假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 或 3 个台阶。你有多少种不同的方法可以爬到楼顶呢? 例如,输入:20 输出:121415
时间: 2024-06-15 11:07:35 浏览: 147
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
5星 · 资源好评率100%
要计算爬楼梯的不同方法数,可以使用动态规划的方法。假设到达第 i 阶楼梯的方法数为 dp[i],则有以下递推关系:
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
其中,dp[0] = 1,dp = 1,dp = 2。
根据上述递推关系,可以编写代码来计算不同的方法数:
```python
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
return dp[n]
n = 20
result = climbStairs(n)
print(result)
```
输出结果为:121415
阅读全文