假设一段楼梯共15个台阶,小明一步最多能上3个台阶。编写程序计算小明上这段楼梯一共有多少种方法。要求给出递推法和递归法两种代码。
时间: 2023-05-31 09:17:53 浏览: 1332
### 回答1:
递推法代码:
```
n = 15 # 台阶数
dp = [] * (n+1) # 初始化dp数组
dp[] = 1 # 初始状态
for i in range(1, n+1):
for j in range(1, 4):
if i >= j:
dp[i] += dp[i-j] # 状态转移方程
print(dp[n]) # 输出结果
```
递归法代码:
```
def climb_stairs(n):
if n == or n == 1:
return 1
elif n == 2:
return 2
else:
return climb_stairs(n-1) + climb_stairs(n-2) + climb_stairs(n-3)
n = 15 # 台阶数
print(climb_stairs(n)) # 输出结果
```
### 回答2:
递推法:
我们可以先用一个长度为16的数组dp来存储到达每一层台阶的方法数,其中dp[i]表示达到第i个台阶的方法数。因为小明一步最多上3个台阶,所以到达第i层的方法数就等于到达第i-1层、第i-2层和第i-3层三种方法数的和。
最后dp[15]即为小明上完这段楼梯的方法数。
下面是递推法的代码实现:
```python
dp = [0] * 16
dp[0] = 1
for i in range(1, 16):
dp[i] = dp[i-1]
if i >= 2:
dp[i] += dp[i-2]
if i >= 3:
dp[i] += dp[i-3]
print(dp[15])
```
递归法:
递归法的思路是通过递归函数f(n)来计算到达第n层台阶的方法数,而f(n)可以分解为:
f(n) = f(n-1) + f(n-2) + f(n-3)
其中f(0) = 1,f(1) = 1,f(2) = 2。
下面是递归法的代码实现:
```python
def climb_stairs(n):
if n == 0 or n == 1:
return 1
if n == 2:
return 2
return climb_stairs(n-1) + climb_stairs(n-2) + climb_stairs(n-3)
print(climb_stairs(15))
```
需要注意的是,递归法可能会存在大量的重复计算,所以在实际应用中会比递推法慢很多。
### 回答3:
递推法代码如下:
```
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] + dp[i - 3]
return dp[-1]
print(climbStairs(15))
```
递推法的思路是,假设当前在第 i 个台阶,有三种上法:
1.从第 i-1 个台阶上来;
2.从第 i-2 个台阶上来;
3.从第 i-3 个台阶上来。
所以,到达第 i 个台阶的方案数为到达第 i-1、i-2、i-3 个台阶的方案数之和。可以使用一个 dp 数组来记录到达每个台阶的方案数。时间复杂度为 O(n)。
递归法代码如下:
```
def climbStairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 4
return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3)
print(climbStairs(15))
```
递归法的思路和递推法一样,只是递归实现。需要注意的是,如果直接使用递归,则会出现大量重复计算。因此,可以使用缓存来优化递归过程。时间复杂度为 O(3^n),但实际时间会因为缓存的使用而有所降低。