python不會的題去哪搜，Python兩種方法求解登樓梯問題（京東2016筆試題）

問題：假設一段樓梯共15個臺階，小明一步最多能上3個臺階，那么小明上這段樓梯一共有多少種方法？

python不會的題去哪搜、解析：從第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種上法（一步邁3個臺階上去、一步2個臺階+一步1個臺階、一步1個臺階+一步2個臺階、一步邁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

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)

看起來是完美的，不過需要注意的是，上面這個遞歸算法貌似簡潔明了，但效率非常非常低，不僅因為遞歸時上下文的保存和恢復比較耗時，還因為涉及大量的重復計算。在Python中，可以使用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)

下面是測試結果，可以看出，普通的遞歸函數效率非常低，應慎重使用。

climbStairs1 ?2555757? 0.0
climbStairs2? 2555757? 458.8922302722931
climbStairs3? 2555757? 0.0