用python编写求楼梯有 n 阶台阶,上楼可以一步上 1 阶,也可以一步上 2 阶,走完 n 阶台阶共有多少种不同的走法。的程序
时间: 2024-05-08 18:16:53 浏览: 20
递归版本:
```python
def climbStairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return climbStairs(n-1) + climbStairs(n-2)
```
动态规划版本:
```python
def climbStairs(n: int) -> int:
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]
```
其中,dp[i] 表示走到第 i 阶台阶的不同走法数。初始值 dp[1] = 1 和 dp[2] = 2。根据题意,走到第 i 阶台阶有两种情况:从第 i-1 阶台阶走1步上来,或从第 i-2 阶台阶走2步上来。因此,dp[i] = dp[i-1] + dp[i-2]。最终返回 dp[n] 即可。