python假设一段楼梯共 15 个台阶,小明一步最多能上 3 个台阶。编写程序计算小明上这段楼 梯一共有多少种方法。要求给出递推法和递归法两种代码
时间: 2024-02-22 17:57:22 浏览: 24
递推法代码:
```python
def climbStairs(n):
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 4
dp = [0] * (n+1)
dp[1], dp[2], dp[3] = 1, 2, 4
for i in range(4, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
return dp[n]
print(climbStairs(15))
```
递归法代码:
```python
def climbStairs(n):
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(n),其中递推法是自底向上的动态规划,递归法是自顶向下的动态规划。