共有9级台阶,一次可以登上1或2级台阶,有多少种方法?

Question

一共有多少种不同的方法?

Answer 1

假设最后一步到X级台阶，有F(X)种走法，
这题求的就是F(9)
因为每步可以迈1或2级台阶。
所以最后一步到9级台阶，
而倒数第2步可能是在第8或7级台阶。
所以到9级台阶的走法，是到第8或7级台阶走法的和。
同样到7级台阶的走法，是到第5或6级台阶走法的和。
...................
F（9）
=F（7）+F（8）
=2F(7)+F(6)
=3F(6)+2F(5)
=5F(5)+3F(4)
=8F(4)+5F(3)
=13F(3)+8F(2)
=21F(2)+13F(1)

因为：上1级台阶只有1种走法，所以F(1)=1。
上2级台阶有2种走法，1步1步走或1次走2步。所以F(2)=2

F（9）==21F(2)+13F(1)
=21*2+13*1
=42+13
=55
上8级台阶一共有55不同的迈法。

参考资料：http://zhidao.baidu.com/question/22333601.html?si=1

Answer 2

yizhong