小明要登9级台阶,每步只能登1级或2级,共有多少种不同的登法?

假设最后一步到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不同的迈法.

全是1的一种
一个2的8种
两个2的16种
三个2的56种
四个2的8种
一共89种

分类思考:2级用N次
0次2级:全是1步:1种
1次2级:7个1步:2级的有8个位置可以放:8种
2次2级:5个1步:6*7/2=21种
3次2级:3个1步:4*5*6/(3*2*1)=20种
4次2级:1个1步:5种
所以一共55种