问题：假设一段楼梯共15个台阶，小明一步最多能上3个台阶，那么小明上这段楼梯一共有多少种方法？
解析：从第15个台阶上往回看，有3种方法可以上来（从第14个台阶上一步迈1个台阶上来，从第13个台阶上一步迈2个台阶上来，从第12个台阶上一步迈3个台阶上来），
同理，第14个、13个、12个台阶都可以这样推算，从而得到公式f(n) = f(n-1) + f(n-2) + f(n-3)，其中n=15、14、13、...、5、4。然后就是确定这个递归公式的结束条件了，
第一个台阶只有1种上法，第二个台阶有2种上法（一步迈2个台阶上去、一步迈1个台阶分两步上去），第三个台阶有4种上法。
Python实现
1.递推法
def climbStairs1(n): a = 1 b = 2 c = 4 for i in range(n-3): c, b, a = a+b+c, c, b return c
2.递归法
def climbStairs2(n): first3 = {1:1, 2:2, 3:4} if n in first3.keys(): return first3[n] else: return climbStairs2(n-1) + \ climbStairs2(n-2) + \ climbStairs2(n-3)
看起来，问题似乎解决了。但是再多考虑一点，方法2中使用递归效率非常低，不仅因为递归时上下文的保存和恢复比较耗时，还因为涉及大量的重复计算。
因此进一步改进，可使用functools标准库提供的缓冲修饰器lru_cache来缓解这个问题。
@functools.lru_cache(maxsize=64)def climbStairs3(n): #带缓冲的递归法 first3 = {1:1, 2:2, 3:4} if n in first3.keys(): return first3[n] else: return climbStairs3(n-1) + \ climbStairs3(n-2) + \ climbStairs3(n-3)
下面是测试代码 ，运行一次就可以看出不缓冲的递归方法效率之低。
n = 25for f in (climbStairs1, climbStairs2, climbStairs3): start = time.time() for i in range(1000): result = f(n) delta = time.time() - start print(f.__name__, result, delta)
Java实现
1.递推法
public static int climbStairs1(int n){ int a = 1; int b = 2; int c = 4; for(int i=0;i<n-3;i++){ c = a + b + c; b = c - a - b; a = c - b - a; } return c; }
2.递归法
public static int climbStairs2(int n){ int first[] = new int[3]; first[0] = 1; first[1] = 2; first[2] = 4; if(n<=3){ return first[n-1]; } else{ return climbStairs2(n-1) + climbStairs2(n-2) + climbStairs2(n-3); } }
本文永久更新链接地址：http://www.xuebuyuan.com/Linux/2017-02/140913.htm
以上就上有关Python求解登楼梯问题（京东2016笔试题）的相关介绍，要了解更多京东2016笔试题,京东笔试题,Python求解登楼梯问题（京东2016笔试题）,编程,Linux编程,Linux Shell,Android,Android教程,JAVA,C语言,Python,HTML5内容请登录学步园。