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?
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
def climbStairs(self, n: int) -> int:
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1]Runtime: 20 ms, faster than 98.10% of Python3 online submissions for Climbing Stairs.
Memory Usage: 14.3 MB, less than 10.74% of Python3 online submissions for Climbing Stairs.