某人上楼梯,一步可以跨上1个台阶,2个台阶,或者3个台阶.共有12个台阶,从地面走上去有多少种不同走法?

问题描述:

某人上楼梯,一步可以跨上1个台阶,2个台阶,或者3个台阶.共有12个台阶,从地面走上去有多少种不同走法?

设P(x)是x个台阶的走法总数
P(1) = 1
P(2) = 2 (1+1 或 2)
P(3) = 4 (1+1+1, 1+2, 2+1, 3)
x >= 4时, 最后一步可以走1或2或3阶,所以P(x) = P(x-1)+P(x-2)+P(x-3)
所以
1 2 4 7 13 24 44 81 149 274 504 927
答案是927

设有n阶台阶,既然一次只能走一步或2步或3步,那么假设现在仅剩下最后一步要走,有三种情况:一 只需要走一步,这时已经走了(n-1)阶,走法与走n-1阶相同,有f(n-1)阶走法; 二 只需要走两步,同上分析有f(n-2); ...