问题

有 n 个阶梯，每次可以往下走 1 步、2 步、3 步，求从顶部回到地面有多少种走法？

思路

第一个台阶，有 1 种走法

第二个台阶，有 2 种走法：

• 第一次走 1 步，第二次走 1 步
• 走 2 步

第三个台阶，有 4 种走法：

• 第一次走 3 步，直接回到地面
• 第一次走 2 步，第二次走 1 步
• 第一次走 1 步，到达第二个台阶，根据上面的推导从第二个台阶到地面有 2 种走法

设数组 D[] 的第 i 个分量表示第 i 个台阶的走法，且 D[0] = 0，则第 N 个台阶的走法有：

• 第一次走 3 步，到达第 N - 3 个台阶，共有 D[N - 3] 种走法
• 第一次走 2 步，到达第 N - 2 个台阶，共有 D[N - 2] 种走法
• 第一次走 1 步，到大第 N - 1 个台阶，共有 D[N - 1] 种走法

所以D[N] = D[N - 3] + D[N - 2] + D[N - 1]。

Python 实现

xxxxxxxxxx
def d(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
​
    return d(n - 3) + d(n - 2) + d(n - 1)
​

将子问题进行缓存，减少重复计算：

xxxxxxxxxx
# coding: utf8
​
​
CACHED_SIZE = 10
​
​
def cache(f):
    # 简易的 LRU cache
    cached_result = {}
    cached_keys = []
​
    def wrapper(n):
        if n not in cached_result:
            if len(cached_keys) == CACHED_SIZE:
                cached_result.pop(cached_keys.pop(0))
            r = f(n)
            cached_result[n] = r
            cached_keys.append(n)
        else:
            cached_keys.remove(n)
            cached_keys.append(n)
        return cached_result[n]
​
    return wrapper
​
​
@cache
def d(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
​
    return d(n - 3) + d(n - 2) + d(n - 1)
​
​
if __name__ == "__main__":
    print(d(1000))
  

获取 Python 程序的最大递归深度：

xxxxxxxxxx
import sys
print(sys.getrecursionlimit())
​

优化成递推：

xxxxxxxxxx
# coding: utf8
​
​
def d(n):
    if n == 0:
        return 0
​
    # 数组的三个分量分别表示前 n - 3 次、n - 2 次、n - 1 次的走法
    tmp = [1, 2, 4]
    if n <= 3:
        return tmp[n - 1]
​
    for ind in range(4, n):
        tmp.append(tmp[0] + tmp[1] + tmp[2])
        tmp.pop(0)
​
    # 返回前三次的和
    return sum(tmp)
​
​
if __name__ == "__main__":
    print(d(5))
​