. 一个n阶楼梯,你站在底部,每次可以选择走1阶或者2阶,问:你走到楼梯顶部有多少种走法?
时间: 2024-05-09 14:20:36 浏览: 11
当n=1时,只有一种走法:1步
当n=2时,有两种走法:一次走2步或分两次走每次走1步
当n=3时,有三种走法:第一步走1步,后面有两阶还有两种走法;第一步走2步,后面有一阶还有一种走法
当n=4时,有五种走法:第一步走1步,后面有三阶还有三种走法;第一步走2步,后面有两阶还有两种走法
当n=5时,有八种走法:第一步走1步,后面有四阶还有五种走法;第一步走2步,后面有三阶还有三种走法
以此类推,可以发现,走到n阶楼梯的走法数量,等于走到n-1阶楼梯的走法数量加上走到n-2阶楼梯的走法数量。因此可以使用递归或动态规划来解决该问题。
递归解法:
```python
def climbStairs(n):
if n == 1:
return 1
if n == 2:
return 2
return climbStairs(n-1) + climbStairs(n-2)
```
动态规划解法:
```python
def climbStairs(n):
if n == 1:
return 1
if n == 2:
return 2
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
```
以上两种解法时间复杂度均为O(n),空间复杂度均为O(n)。也可以使用滚动数组来优化空间复杂度,将空间复杂度降为O(1)。