Python求解登樓梯問題（京東2016筆試題）

問題：假設一段樓梯共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 = 25
for 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);
}
}