70. Climbing Stairs
EasyLeetCodeYou 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?
Example 1
Input: n =
2
Output:
2
Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
Example 2
Input: n =
3
Output:
3
Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
Constraints
1 <= n <= 45
How to solve the problem
- Recursion with Memoization
python
class Solution:
def climbStairs(self, n: int) -> int:
@cache
def dfs(i):
if i <= 1:
return 1
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
- Dynamic Programming
python
class Solution:
def climbStairs(self, n: int) -> int:
f = [0] * (n + 2)
f[0] = f[1] = 1
for i in range(n):
f[i + 2] = f[i + 1] + f[i]
return f[n]
- Optimized Dynamic Programming
python
class Solution:
def climbStairs(self, n: int) -> int:
f0 = f1 = 1
for i in range(2, n + 1):
f = f0 + f1
f0 = f1
f1 = f
return f1
Complexity
- Approach 1 (Recursion with Memoization): Time complexity: O(n), Space complexity: O(n)
- Approach 2 (Dynamic Programming): Time complexity: O(n), Space complexity: O(n)
- Approach 3 (Optimized DP): Time complexity: O(n), Space complexity: O(1)
Comments
No comments yet. Be the first to comment!