计算小明爬楼梯的爬法数量 假设一段楼梯共15个台阶,小明一步最多能上3个台阶。编写程序计算小明上这段楼梯一共有多少种方法。要求给出递推法和递归法两种代码。【将递推法和递归法封装成两个函数】
时间: 2024-10-21 07:17:32 浏览: 2
小明爬楼梯的问题可以用动态规划(Dynamic Programming)中的递推法则解决,也可以通过递归算法来实现。这里我会分别提供递推法和递归法的Python代码示例:
**递推法(使用数组):**
```python
def climb_stairs_dp(steps):
dp = [0] * (steps + 1)
dp[0], dp[1], dp[2] = 1, 1, 2 # 初始化前三步的情况
for i in range(3, steps + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] # 每一级有三种情况,前一步、前两步或前三步
return dp[steps]
# 测试
print(climb_stairs_dp(15))
```
**递归法:**
```python
def climb_stairs_recursion(steps):
if steps <= 3:
return steps
else:
return climb_stairs_recursion(steps - 1) + climb_stairs_recursion(steps - 2) + climb_stairs_recursion(steps - 3)
# 测试
print(climb_stairs_recursion(15))
```
递归法可能会因为大量的重复计算导致效率较低,适合于较小规模的问题;而递推法通过保存中间结果避免了重复计算,适用于大规模问题。
阅读全文