Question

有20阶楼梯，一次只能走1阶或2阶，共有几种走法？

Answer 1

这个题最简单的做法就是分析法。
就是假设阶梯有N层，则按N=1，2，3，4……逐步分析
推出一般规律，即走法a(n)=a(n-2)+a(n-1)可以看出这是一个递推公式。
同时也满足菲波拉契数列的情况
所以20级阶梯的走法a(20)就为菲波拉契数列的第20项
a(20)=fib(20)=10946

另外一种就比较复杂，根据走2步的不同情况分析，最少一个2步都不走，最多为10个。（也可以根据1步，但太多了。）
(1)一个2步都不走，为1种情况。
(2)走1个2步，总共步数为19，从19个中随便选1个为2步的 C（19，1）
(3)走2个2步，总共步数18，从18个中随便选2个为2步的。C（18，2）
依次类推为C（17，3）；C（16，4）；C（15，5）……C（10，10）
总走法=1+C（19，1）+C（18，2）+C（17，3）+……+C（10，10）
=1+19+153+ 680+1820+……+1=10946