面试题目：有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，请问小明登上这段楼梯有多少种不同的走法?

本文主要是介绍面试题目：有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，请问小明登上这段楼梯有多少种不同的走法?，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://www.nowcoder.com/questionTerminal/360069ca7225478380ffdcfb7e4b2a2b
来源：牛客网

 假设走n步阶梯的方法总数为f(n)，那么对于n步的阶梯，有三种情况：第一步走一步，第一步走两步，第一步走三步，
 走完第一步后剩下的走法分别有f(n-1)，f(n-2)，f(n-3)种走法，
所以有:  f(n)=f(n-1)+f(n-2)+f(n-3)               (对于n>=4) 
 同理：       f(n-1)=f(n-2)+f(n-3)+f(n-4)    (对于n>=5) 
 前面两式相减可以得到：  f(n)=2*f(n-1)-f(n-4)  (对于n>=5)
 而对于n<=5的情况有： 
 f(1)=1 
 f(2)=2 
 f(3)=4 
f(4)=7 
于是有： 
f(5)=2*7-f(1)=13 
(6)=2*13-f(2)=24 
 f(7)=2*24-f(3)=44 
f(8)=88-f(4)=81 
f(9)=2*81-f(5)=149 <
f(10)=298-f(6)=274 
f(11)=548-f(7)=504 
f(12)=1008-f(8)=927 
f(13)=1854-f(9)=1854-149=1705 
 f(14)=3410-f(10)=3410-274=3136 
f(15)=6272-f(11)=6272-504=5768 

这篇关于面试题目：有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，请问小明登上这段楼梯有多少种不同的走法?的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！