编程要求:梯有N阶,上楼可以一步上一阶,也可以一次上二阶。编一个程序,计算共有多少种不同的走法
时间: 2024-11-24 19:41:11 浏览: 25
这是一个经典的动态规划问题,通常被称为“爬楼梯”或“斐波那契数列”的变体。我们可以使用动态规划的方法来解决这个问题,其中最直接的思想就是定义一个数组来存储每阶楼梯到达的不同走法数量。
假设 `dp[i]` 表示到达第 `i` 阶楼梯的总走法数,那么有两种情况:
1. 如果上一步是一阶,那么从第一阶到第 `i` 阶可以有 `dp[i-1]` 种走法;
2. 如果上一步是两阶,那么从第二阶到第 `i` 阶可以有 `dp[i-2]` 种走法。
因此,总的走法数 `dp[i]` 就是这两种情况走法数之和:`dp[i] = dp[i-1] + dp[i-2]`。
对于边界条件,当 `i` 为1或2时,只有一种走法(分别是从地上直接上一阶和一步上两阶)。
下面是 Python 代码来实现这个算法:
```python
def climb_stairs(n):
if n <= 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 2
else:
dp = [0] * (n+1) # 创建一个长度为 n+1 的列表来存储结果
dp[1], dp[2] = 1, 2 # 初始化前两步的走法
for i in range(3, n+1): # 从第三阶开始
dp[i] = dp[i-1] + dp[i-2] # 动态更新走法数
return dp[n]
# 测试代码
n = int(input("请输入楼梯的阶数:"))
print(f"上 {n} 阶楼梯的走法总数是:{climb_stairs(n)}")
```
阅读全文