问题:有一个有着n级台阶的楼梯,从最底下往上走,每一步只能向上1级或者2级台阶,求一共有多少种走法。 例:如图, 到第二级台阶有2种方法, 到第四级台阶有5种方法, 到第六级台阶有13种方法。 数据说明:共十个测试点,1<=级数<=77。
时间: 2024-01-18 20:04:05 浏览: 33
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
5星 · 资源好评率100%
这是一个经典的动态规划问题,可以使用递推的方式来计算。具体方法如下:
定义一个长度为 n+1 的数组 dp,其中 dp[i] 表示到达第 i 级台阶的走法总数。
初始化 dp[1] = 1 和 dp[2] = 2,即到达第一级台阶只有一种走法,到达第二级台阶有两种走法。
然后对于 i > 2,有两种情况:
- 从第 i-1 级台阶走一步到达第 i 级台阶,此时走法总数为 dp[i-1]。
- 从第 i-2 级台阶走两步到达第 i 级台阶,此时走法总数为 dp[i-2]。
因此,dp[i] = dp[i-1] + dp[i-2]。
最终的结果为 dp[n]。
以下是 Python 代码实现:
```
def climbStairs(n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
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]
```
输入不同的 n 值,可以得到相应的结果。
阅读全文