EasyBlind75DPMath
Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Examples
Input
n = 2
Output
2
1. 1 step + 1 step, 2. 2 steps.
Input
n = 3
Output
3
1. 1+1+1, 2. 1+2, 3. 2+1.
Constraints
- •
1 <= n <= 45
Approaches
Recursively try climbing 1 or 2 steps.
CodeT: O(2^n) | S: O(n)
def climb_stairs(n):
if n <= 1:
return 1
return climb_stairs(n - 1) + climb_stairs(n - 2)Use dynamic programming to store results of subproblems.
CodeT: O(n) | S: O(n)
def climb_stairs(n):
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Only keep track of the last two values.
Diagram
n=5
a=1,b=1
i=2: a=1,b=2
i=3: a=2,b=3
i=4: a=3,b=5
i=5: a=5,b=8
Result: 8
CodeT: O(n) | S: O(1)
def climb_stairs(n):
if n <= 1:
return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^n) | O(n) | Recursively try climbing 1 or 2 steps. |
| DP - Bottom Up | O(n) | O(n) | Use dynamic programming to store results of subproblems. |
| DP - Space Optimized | O(n) | O(1) | Only keep track of the last two values. |
Recursion
T: O(2^n)S: O(n)
Recursively try climbing 1 or 2 steps.
DP - Bottom Up
T: O(n)S: O(n)
Use dynamic programming to store results of subproblems.
DP - Space Optimized
T: O(n)S: O(1)
Only keep track of the last two values.
Common Mistakes
Using recursion without memoization (exponential time)
Not handling the base cases (n=0, n=1)
Using extra space when O(1) solution is possible