有一个楼梯n级台阶,每次可以上一级或两级台阶,有几种不同上法?

Question

有一个楼梯n级台阶,每次可以上一级或两级台阶,有几种不同上法?

Answer 1

这是一个经典的递归问题.也就是费波纳西级数.
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=3时,2+3=5种走法
(希望你能听得明白)