一段楼梯共23级,每步至多跨3级,问一共有多少种走法

Question

一段楼梯共23级,每步至多跨3级,问一共有多少种走法

Answer 1

设有x级楼梯的走法有f(x)种
f(1)=1 (1)
f(2)=2 (1+1,2)
f(3)=4 (1+1+1,1+2,2+1,3)
而当x>3时,满足f(x)=f(x-1)+f(x-2)+f(x-3) (x>3)
这是因为最后一步只有三种可能,走1级、2级、3级.
其走法数之和就是走x级楼梯结果,而最后走1级的走法数,就是走x-1级楼梯的走法数.
同理,得出最后走2级和3级的走法数.
则f(23)=755476.
PS：我直接用程序算出结果.