腾讯面试题:50个阶梯,走上去,共有多少种走

如题所述

这个题最简单的做法就是分析法。
就是假设阶梯有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
温馨提示:答案为网友推荐,仅供参考
相似回答