上台阶,有n级台阶(n>0),从下面开始走要走到所有台阶上面,每步可以走一级或两级,问有多少种不同的走法。
时间: 2024-02-17 15:04:49 浏览: 15
这是一个经典的动态规划问题。假设我们要走到第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种不同的走法可以从第一级台阶走到第五级台阶。
相关问题
2.上台阶,有n级台阶(n>0),从下面开始走要走到所有台阶上面,每步可以走一级或两级,问有多少种不同的走法。
这是一个典型的斐波那契数列问题,可以用递归或循环实现。具体实现如下:
方法一:递归实现
```python
def climbStairs(n):
if n == 1:
return 1
if n == 2:
return 2
return climbStairs(n-1) + climbStairs(n-2)
```
方法二:循环实现
```python
def climbStairs(n):
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 2
for i in range(3, n+1):
a, b = b, a + b
return b
```
其中,递归实现更容易理解,但是当 n 很大时,会出现递归深度过深的情况,导致程序崩溃。循环实现则没有这个问题,而且效率更高。
用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,程序会输出有多少种不同的走法。