Climbing Stairs
Easyways(i) = ways(i−1) + ways(i−2) · Fibonacci
Ways to reach a step = ways to the step below + ways to the one two below (it's Fibonacci!).
The idea
To reach step i you either took a single step from i−1 or a double step from i−2. So the number of ways is the sum of those two — the Fibonacci recurrence.
calls1
Step 1 of 7. Brute force: ways(5) calls ways(4) and ways(3) — and each of those splits again. calls 1.
1/7
Brute force
timeO(2ⁿ)spaceO(n)
Exponential tree.
1function ways(n) {2 if (n <= 1) return 1;3 return ways(n - 1) + ways(n - 2); // same calls over and over4}Input
- nodes
- 1, 0 edges
Memory
- calls
- 1
- ways(1) redone
- —
- brute calls
- —
Call stack
- 0visit(ways(5))
Output
- with memo
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 2
- Output:
- 2
- Explanation:
- Two ways: 1+1 or a single 2-step.
Example 2
- Input:
- n = 3
- Output:
- 3
- Explanation:
- 1+1+1, 1+2, or 2+1 → 3 ways.
Example 3
- Input:
- n = 5
- Output:
- 8
- Explanation:
- The count follows Fibonacci → 8.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.