上台阶问题:有n级台阶,每步可以走一级或两级,问有多少种不同的走法python
时间: 2024-05-13 10:16:13 浏览: 14
可以使用递归或动态规划来解决这个问题。
方法一:递归
递归的思路是,如果当前在第n级台阶上,则可以走一步到达n-1级台阶,或者走两步到达n-2级台阶。因此,到达第n级台阶的不同走法数就是到达n-1级台阶和到达n-2级台阶的不同走法数之和。
代码如下:
```python
def climbStairs(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return climbStairs(n-1) + climbStairs(n-2)
```
方法二:动态规划
动态规划的思路是,用一个数组dp来记录到达每个台阶的不同走法数。初始状态是dp[1]=1和dp[2]=2,然后根据递推公式dp[i]=dp[i-1]+dp[i-2],依次计算出dp[3]、dp[4]、...、dp[n]。
代码如下:
```python
def climbStairs(n):
if n == 1:
return 1
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]
```
两种方法的时间复杂度都是O(n),但是递归方法的空间复杂度比较高,可能会导致栈溢出,因此建议使用动态规划方法。
相关问题
上台阶,有n级台阶(n>0),从下面开始走要走到所有台阶上面,每步可以走一级或两级,问有多少种不同的走法。
这是一个经典的动态规划问题。假设我们要走到第n级台阶,有两种情况:
1. 最后一步走了1级台阶,那么此时我们需要从第n-1级台阶走到第n级台阶,共有f(n-1)种走法。
2. 最后一步走了2级台阶,那么此时我们需要从第n-2级台阶走到第n级台阶,共有f(n-2)种走法。
因此,走到第n级台阶的总走法数为f(n) = f(n-1) + f(n-2)。
而当n=1时,只有一种走法,当n=2时,有两种走法。
因此,我们可以用动态规划的方法,从n=3开始,依次计算出f(3)、f(4)、f(5)……直到f(n),最终输出f(n)即可。
下面是一个Python实现的示例代码:
```python
def climb_stairs(n):
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]
return dp[n]
```
例如,如果n=5,调用climb_stairs(5)会返回8,表示有8种不同的走法可以从第一级台阶走到第五级台阶。
用Python编写程序满足2. 上台阶,有n级台阶(n>0),从下面开始走要走到所有台阶上面,每步可以走一级或两级,问有多少种不同的走法。
可以使用递归来解决这个问题,如下是Python代码实现:
```python
def climb_stairs(n):
"""
计算n级台阶有多少种不同的走法
"""
if n == 1:
return 1
if n == 2:
return 2
return climb_stairs(n - 1) + climb_stairs(n - 2)
n = int(input("请输入台阶的级数:"))
print("有%d种不同的走法。" % climb_stairs(n))
```
运行程序后,输入台阶的级数n,程序会输出有多少种不同的走法。