假设最后一步到X级台阶,有F(X)种走法,
这题求的就是F(20) 因为每步可以迈2级台阶或3级台阶.
所以最后一步到20级台阶,而倒数第2步可能是在第18或17级台阶.
所以到20级台阶的走法,是到第18或17级台阶走法的和.
同样到17级台阶的走法,是到第15或16级台阶走法的和..
F(20)
=F(17)+F(18)
=2F(17)+F(16)
=3F(16)+2F(15)
=5F(15)+3F(14)
=8F(14)+5F(13)
=13F(13)+8F(12)
=21F(12)+13F(11)
=34F(11)+21F(10)
=55F(10)+34F(9)
=89F(9)+55F(8)
=144F(8)+89F(7)
=233F(7)+144F(6)
=377F(6)+233F(5)
=610F(5)+377F(4)
因为:上4级台阶只有1种走法,所以F(4)=1.
上5级台阶有2种走法,1次2步走2次走3步或1次走3步再走2步.所以F(5)=2
F(20)
=610F(5)+377F(4)
=610*2+377
=1220+377=1597
上20级台阶一共有1597不同的迈法.