Find the number of different ways to climb a 9-stage ladder when each step is either one or two stages. (For example, a 2-stage ladder can be climbed two ways: 1-1, and 2.)
时间: 2024-02-23 21:03:05 浏览: 120
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
5星 · 资源好评率100%
这个问题可以使用动态规划算法来解决。我们可以定义一个数组 `ways`,其中 `ways[i]` 表示登上第 `i` 个阶梯的不同方法数。
对于第一个阶梯和第二个阶梯,它们可以分别被登上的方式是 1 和 2,因此 `ways[1] = 1`,`ways[2] = 2`。
对于第三个阶梯,我们可以从第一阶梯直接跨两步上来,也可以从第二阶梯跨一步上来。因此有 `ways[3] = ways[2] + ways[1]`。
对于第四个阶梯,我们可以从第三个阶梯跨一步上来,也可以从第二个阶梯跨两步上来。因此有 `ways[4] = ways[3] + ways[2]`。
以此类推,我们可以得到如下的递推式:
```
ways[i] = ways[i-1] + ways[i-2]
```
最终,我们可以得到登上第9个阶梯的不同方法数为 `ways[9] = 55`。
以下是 Python 代码实现:
```python
n = 9
ways = [0] * (n+1)
ways[1] = 1
ways[2] = 2
for i in range(3, n+1):
ways[i] = ways[i-1] + ways[i-2]
print(ways[9])
```
阅读全文