这是一个经典的递归问题. 也就是费波纳西级数.
f(n) = f(n-1) + f(n-2).
如果我们第一部选 1 个台阶, 那么后面就会剩下 n-1 个台阶, 也就是会有 f(n-1) 种走法. 如果我们第一部选 2 个台阶, 后面会有 f(n-2) 个台阶. 因此, 对于 n 个台阶来说, 就会有 f(n-1) + f(n-2) 种走法.
因此, 1 个台阶 f(1) = 1.
- f(2) = 2,
- f(3) = 3
- f(4) = 5
- f(5) = 8
- f(6) = 13
- f(7) = 21
- f(8) = 34
- f(9) = 55
- f(10) = 89
- f(11) = 89+55 = 144
- f(12) = 144 + 89 = 233
- .
- 2.
这类题可这样理解
假设走到第 n 阶有 f(n) 种走法, 走到第 n+1 阶有 f(n+1) 种走法;
则走到第 n+2 阶, 则可分成两种情况:
一, 最后一步是从第 n 阶直接登两级到第 n+2 阶
二, 最后一步是从第 n+1 阶直接登一级到第 n+2 阶
由于从地面到第 n 阶, 和到第 n+1 阶的走法已经知道
故从地面到第 n+2 阶的走法:
f(n+2)=f(n)+f(n+1)
n=1 时, 1 种走法
n=2 时, 2 种走法
n=3 时, 1+2=3 种走法
n=4 时, 2+3=5 种走法
来源: https://www.cnblogs.com/lamp01/p/8486451.html