动态规划：把重复计算记下来

同一个值被算了多少次

爬楼梯：一次能上 1 级或 2 级，走到第 n 级有多少种走法。

按第 12 课的老办法，直接写成递归：走到第 n 级的走法数，等于「先走 1 级再来 n-1 级」加上「先走 2 级再来 n-2 级」。写出来就是 climb(n) = climb(n-1) + climb(n-2)。

import sys
import time

sys.setrecursionlimit(100000)
calls = [0]


def climb_naive(n):
    calls[0] += 1
    if n <= 1:
        return 1
    return climb_naive(n - 1) + climb_naive(n - 2)


def climb_memo(n):
    """记忆化：算过的记在字典里，下次直接取。"""
    memo = {}

    def f(k):
        if k <= 1:
            return 1
        if k not in memo:
            memo[k] = f(k - 1) + f(k - 2)
        return memo[k]

    return f(n)


def climb_iter(n):
    """自底向上递推：从 0 和 1 一路推到 n。"""
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


print('   n   朴素递归调用次数   三版答案')
for n in (20, 25, 30, 34):
    calls[0] = 0
    r1 = climb_naive(n)
    r2 = climb_memo(n)
    r3 = climb_iter(n)
    print(f'  {n:>3}  {calls[0]:>16,}   {r1} {"一致" if r1 == r2 == r3 else "不一致"}')

   n   朴素递归调用次数   三版答案
   20            21,891   10946 一致
   25           242,785   121393 一致
   30         2,692,537   1346269 一致
   34        18,454,929   9227465 一致

调用次数是确定的，每加一级就涨到 6.8 倍左右。耗时则每次跑都不一样，看个数：

（本机实测，跑两遍秒数会在上表这个范围内浮动，所以只当数量级看。递归版那三列里含了一次计数开销，比第 12 课量到的稍慢。）

三版答案完全一样。差别全在代价上：

• 朴素递归算 n=34 要 1845 万次调用、一秒多。
• 记忆化 0.00002 秒上下。
• 递推 0.000005 秒上下。

递推版循环了 32 次。1845 万次调用做的事，和 32 次循环做的事完全一样。

重叠子问题

调用次数为什么爆炸？因为同一个子问题被反复重算。

把次数数出来看：

counts = {}


def climb_count(n):
    counts[n] = counts.get(n, 0) + 1
    if n <= 1:
        return 1
    return climb_count(n - 1) + climb_count(n - 2)


for n in (10, 15, 20, 25, 30):
    counts.clear()
    climb_count(n)
    total = sum(counts.values())
    print(f'  n={n:>2}: 一共 {total:>9,} 次调用，其中 climb(0) 被算了 {counts.get(0, 0):>9,} 次')

  n=10: 一共       177 次调用，其中 climb(0) 被算了        34 次
  n=15: 一共     1,973 次调用，其中 climb(0) 被算了       377 次
  n=20: 一共    21,891 次调用，其中 climb(0) 被算了     4,181 次
  n=25: 一共   242,785 次调用，其中 climb(0) 被算了    46,368 次
  n=30: 一共 2,692,537 次调用，其中 climb(0) 被算了   514,229 次

climb(0) 的值永远是 1，可它被算了 51 万次。这就是「重叠子问题」：递归树里大量的结点其实是同一个子问题，只是走了不同的路径到达。

动态规划的全部起点就是这一件事：把算过的答案记下来。 记下来之后，那个 51 万次变成 1 次。

记忆化搜索

上一步的 climb_memo 就是记忆化：写法还是递归，只是在函数开头先查表，算完把结果写进表。

memo = {}


def f(k):
    if k <= 1:
        return 1          # 边界：不用查表
    if k not in memo:     # 没算过才算
        memo[k] = f(k - 1) + f(k - 2)
    return memo[k]        # 算过就直接取

改动只有三行，代价从 1.37 秒掉到 0.000014 秒。记忆化是最容易上手的动态规划形式：先在朴素递归上把「状态是什么」想清楚，然后加一个字典，不改结构。

记忆化版本的字典里存了多少格？

• n=30：29 项
• n=100：99 项
• n=1000：999 项

也就是 O(n) 格。递归总共只会真正算出 n 个不同的子问题——剩下的 1800 万次调用全都被字典挡住了。

自底向上递推

climb_iter 是另一条路：不递归，从最小的问题开始，一格一格往外推。

def climb_iter2(n):
    if n <= 1:
        return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

a 存第 i-2 级的走法数，b 存第 i-1 级的，每循环一次就把两者相加得到下一个。它比记忆化还快一点，而且只用了两个变量——记忆化要开一个字典存 n 项，递推只要存最近两项。

代价是递推版本更难写：你得自己决定按什么顺序填表，保证算某一格时它依赖的格子都已经算好了。记忆化不用操心这个，递归会自己按需要往下走。

先用记忆化把答案写对，再考虑改成递推。 反过来容易在填表顺序上卡住。

状态转移与边界

动态规划写之前要回答三个问题，这三件套缺一不可：

1. 状态：dp[...] 里的下标代表什么？一句话说清，比如「dp[i] 是走到第 i 级的走法数」。
2. 转移：dp[i] 由哪些更小的状态算出来？比如 dp[i] = dp[i-1] + dp[i-2]。
3. 边界与初始化：最小的那几个状态值是多少？比如 dp[0] = 1、dp[1] = 1。

三件事里最容易糊弄过去的是第一件。「dp[i] 表示前 i 个的最优值」这种话不算说清——「最优值」是最大值还是最小值？「前 i 个」包不包含第 i 个？说不清，转移方程就写不对。

把状态表画出来

看一道状态有两个下标的题：数字三角形，从塔尖走到塔底，每一步只能走到下一行的相邻位置，求路径上数字之和的最大值。

这次状态是 dp[i][j]：从塔尖走到第 i 行第 j 列的最大和。转移是「从左上或右上过来，取大的那个」。

tri = [
    [7],
    [3, 8],
    [8, 1, 0],
    [2, 7, 4, 4],
    [4, 5, 2, 6, 5],
]


def tri_iter(rows):
    dp = [row[:] for row in rows]
    for i in range(1, len(rows)):
        for j in range(len(rows[i])):
            if j == 0:                                  # 最左边只有一条路
                dp[i][j] += dp[i - 1][0]
            elif j == len(rows[i]) - 1:                 # 最右边也只有一条
                dp[i][j] += dp[i - 1][j - 1]
            else:                                       # 中间从左上或右上取大的
                dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j])
    return dp


dp = tri_iter(tri)
for row in dp:
    print('   ' + '  '.join('%3d' % v for v in row))
print('   答案（最底一行的最大者）:', max(dp[-1]))

     7
    10   15
    18   16   15
    20   25   20   19
    24   30   27   26   24
   答案（最底一行的最大者）: 30

把这张表打印出来，是检查状态定义最快的方法。 第二行那两个数 10 和 15：10 是 7+3，15 是 7+8，符合「从塔尖走下来的最大和」。第三行最左的 18 是 10+8——因为最左列只有一条路。这些数都对得上，说明状态和转移都写对了。

对不上就是状态想错了。比赛时别硬盯代码，把表打出来看。

键漏了参数会怎样

记忆化的键必须包含状态的全部维度。少写一个，两种不同的状态就会撞成同一格，互相覆盖。

把数字三角形的记忆化键从 (i, j) 改成只写 i，试 200 组随机三角形：

import random


def tri_memo(rows, memo, key_of):
    """key_of 决定 memo 的键怎么算——这一版让它可换，好用来看漏参数的后果。"""
    n = len(rows)
    memo.clear()

    def f(i, j):
        if i == n - 1:
            return rows[i][j]
        key = key_of(i, j)
        if key not in memo:
            memo[key] = rows[i][j] + max(f(i + 1, j), f(i + 1, j + 1))
        return memo[key]

    return f(0, 0)


random.seed(13)
bad_cases = 0
for _ in range(200):
    n = random.randint(2, 7)
    rows = [[random.randint(-9, 9) for _ in range(i + 1)] for i in range(n)]
    right = tri_memo(rows, {}, lambda i, j: (i, j))
    wrong = tri_memo(rows, {}, lambda i, j: i)
    if right != wrong:
        bad_cases += 1
print(f'   200 组随机三角形：键写成 (行, 列) 与只写成 行，结果不同的有 {bad_cases} 组')

   200 组随机三角形：键写成 (行, 列) 与只写成 行，结果不同的有 130 组

200 组里错 130 组。 而且错的方式很隐蔽：只写 i 的话，(3, 0) 和 (3, 2) 会被当成同一格，谁先算出来谁就占了这一格，另一个直接读到别人的答案。

这个错误不会报错、不会死循环，只会安静地给出偏小的答案。所以凡是记忆化，写完一定要问一遍：memo 的键里，状态有几个维度就有几个分量吗？

初始化错一位

另一个安静的坑在边界上。爬楼梯的 dp[0] 按定义应该是 1（走 0 级有 1 种走法：什么都不做）。把它写成 0：

def climb_wrong0(n):
    """dp[0] 写成 0——整张表往后偏一位。"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 0          # 应该是 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


print('   n   正确   dp[0]写成0')
for n in range(1, 9):
    print(f'   {n:>2}  {climb_iter(n):>6}  {climb_wrong0(n):>8}')

   n   正确   dp[0]写成0
    1       1         1
    2       2         1
    3       3         2
    4       5         3
    5       8         5
    6      13         8
    7      21        13
    8      34        21

注意右边那一列：它交回的正好是正确序列的前一项。 1、2、3、5、8、13——全都是合法答案，只是整体往后挪了一位。

这就是初始化错误最坏的地方：它不是随机错，是系统性地偏移。拿 n=1 试，两边都是 1，看不出问题；拿 n=2 试才露出来。而如果题目里 n 很大，你会得到一个「看起来很正常」的数，只是不对。

自查办法：拿最小的几个输入手算一遍，跟程序对。 n=0、n=1、n=2 这三个值要对得上，整张表的基准才对。

这一课用到的判断

• 动态规划解决的是「重叠子问题」：朴素递归把同一个子问题算了几十万次，实测 n=30 时 climb(0) 被算了 51 万次。
• 记忆化就是「朴素递归加一个字典」：函数开头查表、算完写表。爬楼梯从一秒多掉到 0.00002 秒上下，代码只多三行。
• 递推是「从最小的问题往外推」：不用递归、常常能把空间压到几项（爬楼梯只要两个变量），但要自己排填表顺序。
• 三件套缺一不可：状态（dp[...] 是什么）、转移（由哪些更小的状态算出来）、边界与初始化。状态定义必须一句话说清，含糊了就写不对转移。
• 记忆化的键要包含状态的全部维度：数字三角形漏掉列，200 组随机数据错 130 组，而且不报错。
• 初始化错误是系统性偏移：爬楼梯 dp[0] 从 1 写成 0，整列答案变成正确序列的前一项。拿 n=0,1,2 手算对一遍就能挡住。
• 把状态表打印出来是最快的自查手段：表格里每一格的含义能跟题目对得上，状态就写对了。
• 先用记忆化写对，再考虑改成递推：顺序反了容易卡在填表顺序上。

• 《算法导论（第 3 版）》第 15 章 动态规划书 · 最优子结构、重叠子问题、自顶向下与自底向上的对照
• OI Wiki · 动态规划基础状态设计、转移方程与记忆化搜索的写法
• 第 12 课：递归：函数调用自己上一课量过的递归调用开销与递归深度上限
• 第 23 课：贪心：每一步都选当前最好贪心证不出来时，换的就是这一课的方法