跳转到内容
← 返回算法
算法范式计算机科学 · 算法约 23 分钟阅读

动态规划

Dynamic Programming

"Dynamic Programming"这个名字，是 Richard Bellman（美国应用数学家）在 1950 年代发明的。他后来在自传里坦承，选这个名字是因为"dynamic"听起来酷，而"programming"在当时意指"规划"（不是写代码），还因为他需要一个让军方资助人"无法反对"的词汇来隐藏他的数学研究…

动态规划最优子结构记忆化状态转移优化算法

"Dynamic Programming"这个名字，是 Richard Bellman（美国应用数学家）在 1950 年代发明的。他后来在自传里坦承，选这个名字是因为"dynamic"听起来酷，而"programming"在当时意指"规划"（不是写代码），还因为他需要一个让军方资助人"无法反对"的词汇来隐藏他的数学研究。

名字虽然来历诡异，这个思想本身却是算法设计中最强大的范式之一——把看似指数复杂度的问题，通过重用计算结果，降到多项式时间。

一个为躲避审查而起的名字

这段轶事值得说全，因为它是科研管理史上一个不常见的标本。1950 年秋，Bellman 在兰德公司（RAND Corporation）研究"多阶段决策过程"，兰德的经费来自美国空军，而空军的顶头上司是时任国防部长查尔斯·威尔逊（Charles Wilson）。按 Bellman 自传《飓风眼》（Eye of the Hurricane, 1984）的说法，威尔逊对"research（研究）"这个词有一种病态的反感——在他面前提这个词，他会脸色发红、当场发作。

于是 Bellman 要给自己的工作起一个"藏得住数学"的名字。他挑了 "dynamic"，因为这个词有时间维度、听上去是多阶段的，而且没有任何贬义可用——"你没法用贬义的方式使用 dynamic 这个词"；再配上 "programming"，当时这个词在运筹学里指的是"排程、规划"（与"linear programming（线性规划）"同源），跟写代码毫无关系。合起来是一个连国会都不会反对的短语。

该记住的不是这个笑话，而是它的后果：一个为通过预算审查而起的名字，让后来七十年的每一届学生在第一节课都要先被告知"它既不 dynamic 也不 programming"。命名是算法教学里最被低估的成本。

破除误解：DP 不是一种固定算法

"动态规划"不是一个特定的算法，而是一种解题范式：把大问题分解为小问题，把小问题的结果存下来，避免重复计算。与贪心算法（每步做局部最优选择）不同，动态规划在子问题上穷举所有可能，但通过记录已算过的子问题结果，避免指数级的重复。

两个充分条件：

  1. 最优子结构：整体问题的最优解，由子问题的最优解组成
  2. 重叠子问题：不同的分解路径会反复遇到同样的子问题（若无重叠，分治法即可，无需 DP，见 divide-and-conquer）

从斐波那契说起

斐波那契数列：$F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)$。朴素递归实现：

python
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
```

看起来简洁，实则指数爆炸：计算 $F(5)$ 需要计算 $F(3)$ 两次、$F(2)$ 三次……$F(n)$ 的调用次数是 O(2n)O(2^n)。原因是大量重复计算，计算树如下：

              F(5)
            /      \
          F(4)     F(3)
         /    \    /  \
       F(3)  F(2) F(2) F(1)
       /  \
     F(2) F(1)
```

记忆化（Memoization）：把算过的值存起来，再遇到直接返回：

python
from functools import lru_cache

@lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) ```

时间复杂度降至 $O(n)$，每个子问题只算一次。

自底向上（Tabulation）：不用递归，按子问题依赖顺序迭代：

python
def fib(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
```

重叠到什么程度：把重复次数数出来

"重叠子问题"是个抽象说法。它到底重叠多少倍？两个例子，数字都可以自己验算。

斐波那契。上面那份朴素递归，函数被调用的总次数记为 $T(n)$，则 $T(0)=T(1)=1$、$T(n)=1+T(n-1)+T(n-2)$，展开可得闭式 $T(n) = 2F(n+1) - 1$。代入 $n=30$：$F(31) = 1346269$，所以

T(30)=2×1346269−1=2 692 537T(30) = 2 \times 1346269 - 1 = 2\,692\,537

269 万次调用，只为了算出 $F(30) = 832040$ 这一个数。 而记忆化之后，不同的参数只有 $0$ 到 $30$ 共 31 个。比值约 8.7 万倍。

最长公共子序列（LCS）。取两个长度均为 10 的字符串，且没有任何公共字符（例如 AAAAAAAAAA 与 BBBBBBBBBB）。此时朴素递归每次都走 max(lcs(i-1,j), lcs(i,j-1)) 这一支，调用次数满足 $T(m,0)=T(0,n)=1$、$T(m,n)=1+T(m-1,n)+T(m,n-1)$，闭式是 T(m,n)=2(m+nm)−1T(m,n) = 2\binom{m+n}{m} - 1。代入 $m=n=10$：

T(10,10)=2(2010)−1=2×184756−1=369 511T(10,10) = 2\binom{20}{10} - 1 = 2 \times 184756 - 1 = 369\,511

而记忆化后的状态数只有 11×11=12111 \times 11 = 121 个。约 3054 倍。

朴素递归调用次数记忆化后状态数倍数
$F(30)$2 692 53731≈ 86 856
LCS(10,10)\text{LCS}(10, 10)369 511121≈ 3054

这张表最该注意的是倍数随规模增长的方式：不是常数，是指数。$F(50)$ 的朴素调用次数超过 4×10104 \times 10^{10}，状态数还是 51。所以记忆化不是"优化了一点"，而是把复杂度类换掉了——从指数换成多项式。反过来也说明：如果一个递归的子问题几乎不重复（如归并排序的左右两半），记忆化只会白占内存。

手算 LIS：两种解法的同一个输入

最长递增子序列（Longest Increasing Subsequence, LIS）：给一个数列，求最长的、下标递增且数值也递增的子序列长度（子序列不要求连续）。这是 DP 里少见的"同一个问题有两个漂亮解法、复杂度还不同"的例子，正好可以并排看。

取输入 A=[2, 5, 3, 7, 11, 8, 10, 13]A = [2,\ 5,\ 3,\ 7,\ 11,\ 8,\ 10,\ 13]。

解法一：$O(n^2)$ 的标准 DP

状态 dpidp_i = 以 AiA_i 结尾的最长递增子序列长度。转移是 dpi=1+max⁡{dpj:j<i, Aj<Ai}dp_i = 1 + \max\{dp_j : j < i,\ A_j < A_i\}（没有合法的 $j$ 时取 1）。逐个填：

$i$12345678
AiA_i25371181013
dpidp_i12234456
最优前驱—225 或 377810

答案是 max⁡idpi=6\max_i dp_i = 6，顺着前驱回溯得到 2→5→7→8→10→132 \to 5 \to 7 \to 8 \to 10 \to 13。注意 dp6=4dp_6 = 4 那一格（A6=8A_6 = 8）：它接在 7 后面而不是 11 后面，因为 $11 > 8$ 不合法——这一格是全表唯一需要"往回看"的地方，也是 O(n2)O(n^2) 的来源：每个 $i$ 都要扫一遍前面所有 $j$。

解法二：$O(n \log n)$ 的尾数组 + 二分

换一个数据布局：维护数组 tails\text{tails}，其中 tails[k]\text{tails}[k] = 所有长度为 $k+1$ 的递增子序列中，最小可能的结尾值。这个数组天然严格递增，于是可以二分。每读入一个新数 $x$，二分找到第一个 ≥x\geq x 的位置：找到就替换，找不到（$x$ 比所有尾都大）就追加。

步读入二分结果动作尾数组
12无 ≥2\geq 2 的尾追加[2]
25无 ≥5\geq 5 的尾追加[2, 5]
33第 2 位的 5替换[2, 3]
47无追加[2, 3, 7]
511无追加[2, 3, 7, 11]
68第 4 位的 11替换[2, 3, 7, 8]
710无追加[2, 3, 7, 8, 10]
813无追加[2, 3, 7, 8, 10, 13]

最终长度 6，与解法一一致。两次"替换"是全部戏剧所在：第 3 步用 3 换掉 5，长度没变（还是 2），但把"长度 2 的子序列"的门槛从 5 降到 3——后面来的 7 因此更容易接上。第 6 步同理，用 8 换掉 11，让 10 得以追加成第 5 位。替换不增加长度，只降低未来的门槛；追加才增加长度。理解这一句，这个算法就不再是背下来的了。

失败现场：把尾数组当成答案

这个算法最常见的误用是直接把最终的尾数组当作那条最长子序列输出。上例里 [2,3,7,8,10,13] 恰好确实是一条合法的递增子序列，容易让人相信这总成立。但它不成立。最小反例只要三个数：

A=[2, 5, 1]A = [2,\ 5,\ 1]

尾数组的演化是 [2] → [2,5] → 1 替换掉 2 → [1,5]。长度 2 是对的（2→52 \to 5 就是一条），但 [1, 5] 不是 $A$ 的子序列——1 在原数列里排在 5 后面。尾数组存的是"每个长度档位当前的最小结尾值"，这些值来自不同时刻、不同的子序列，拼在一起没有顺序含义。要输出真正的子序列，必须额外记每个元素被放进哪个档位时的前驱下标。

这类错误的形状值得记住：O(nlog⁡n)O(n\log n) 的解法之所以更快，往往是因为它丢掉了一部分信息（这里丢掉的是"谁接在谁后面"）。丢掉的东西不会自己回来。

经典问题：最长公共子序列（LCS）

给两个字符串 X=x1x2…xmX = x_1 x_2 \ldots x_m 和 Y=y1y2…ynY = y_1 y_2 \ldots y_n，求它们最长的公共子序列（子序列不要求连续，但保持顺序）。

状态定义：$dp[i][j]$ = $X$ 的前 $i$ 个字符和 $Y$ 的前 $j$ 个字符的最长公共子序列长度。状态转移方程：

dp[i][j]={dp[i−1][j−1]+1if xi=yjmax⁡(dp[i−1][j], dp[i][j−1])if xi≠yjdp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } x_i = y_j \\ \max(dp[i-1][j],\ dp[i][j-1]) & \text{if } x_i \neq y_j \end{cases}

python
def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]
```

时间复杂度：$O(mn)$，空间：$O(mn)$（可优化为 O(min⁡(m,n))O(\min(m,n))）。LCS 是 diff（比较两个文件差异的命令行工具）的核心算法，也用于生物信息学中的 DNA/蛋白质序列比对。

背包问题：离散优化的原型

0/1 背包问题：$n$ 件物品，第 $i$ 件重量 wiw_i，价值 viv_i。背包容量 $W$，每件物品选或不选，求最大总价值。状态 $dp[i][j]$ = 前 $i$ 件物品在容量 $j$ 下的最大价值，转移是

dp[i][j]=max⁡(dp[i−1][j], dp[i−1][j−wi]+vi)dp[i][j] = \max\left(dp[i-1][j],\ dp[i-1][j-w_i] + v_i\right)

第一项：不选第 $i$ 件；第二项：选第 $i$ 件（前提是装得下）。时间 $O(nW)$，空间 $O(nW)$（可优化为 $O(W)$）。

背包问题是许多实际优化问题的抽象：资源分配、投资组合、任务调度。它也是"伪多项式时间"这个概念最标准的载体——完整的 DP 表逐格走查、一维滚动数组的方向陷阱、以及 $O(nW)$ 为什么其实是指数时间，见 knapsack-problem。

编辑距离：拼写纠错背后的 DP

编辑距离（Levenshtein Distance）：把字符串 $A$ 转化为字符串 $B$ 所需的最少操作数，每次操作可以是插入、删除或替换一个字符。

例如，"kitten" → "sitting"（编辑距离为 3）：

  1. kitten → sitten（替换 k 为 s）
  2. sitten → sittin（替换 e 为 i）
  3. sittin → sitting（插入 g）

DP 定义：$dp[i][j]$ = 把 $A$ 的前 $i$ 个字符变为 $B$ 的前 $j$ 个字符所需的最少操作数。

dp[i][j]={dp[i−1][j−1]if A[i]=B[j]（无需操作）1+min⁡(dp[i−1][j], dp[i][j−1], dp[i−1][j−1])否则（删/插/替）dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } A[i] = B[j] \text{（无需操作）} \\ 1 + \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]) & \text{否则（删/插/替）} \end{cases}

时间和空间均为 $O(mn)$，可优化到 O(min⁡(m,n))O(\min(m, n)) 空间。实际应用：拼写检查器（"你是否想搜索 X？"）、DNA 序列比对（Smith-Waterman 变体）、diff 工具（Git 中两个文件版本的对比）、语音识别的词错误率（WER）计算。

另一个视角：DP 与最短路径

动态规划可以看作有向无环图（DAG）上的最短（或最长）路径问题：

  • 每个"状态"是 DAG 上的一个节点
  • "状态转移"是 DAG 的边
  • 求最优解等价于求 DAG 上的最短/最长路径

这把 DP 和图算法统一进同一框架。Dijkstra 对一般加权图求最短路径；DP 在 DAG（无环图）上求最短路径，可以线性时间完成（因为 DAG 有拓扑序）。

状态设计的艺术

DP 的难点不在代码，在状态定义。状态设计得好，转移简单；设计不好，问题根本无法正确求解。常见陷阱有两类：状态维度不够（遗漏了区分子问题所需的关键信息），或状态维度过多（时间空间复杂度爆炸）。

实践中，识别 DP 问题的信号：问题要求"最大/最小/多少种方案"；问题可以分解为较小的同类子问题；且子问题之间有依赖关系（不是独立的）。

失败现场：漏一维，答案就变成另一个问题

抽象地说"维度不够"没有说服力，看一个能手算的。题目：硬币面额 {1,2}\{1, 2\}，问凑出金额 3 有多少种组合（不计顺序，$1+2$ 与 $2+1$ 算同一种）。正确答案是 2：$1+1+1$ 和 $1+2$。

一个自然但错误的状态是 $dp[j] = $ "凑出金额 $j$ 的方案数"，然后外层枚举金额、内层枚举硬币：

python
dp = [0] * (amount + 1)
dp[0] = 1
for j in range(1, amount + 1):        # 外层：金额
    for c in coins:                   # 内层：硬币
        if j >= c:
            dp[j] += dp[j - c]
```

逐格算一遍（coins = [1, 2]，amount = 3）：

金额 $j$用硬币 1：$dp[j-1]$用硬币 2：$dp[j-2]$$dp[j]$
0——1（初始）
1$dp[0]=1$放不下1
2$dp[1]=1$$dp[0]=1$2
3$dp[2]=2$$dp[1]=1$3

得到 3，多了一个。多出来的正是 $2+1$——它和 $1+2$ 被当成了两种。把两层循环换个顺序（外层硬币、内层金额）就对了：

阶段$dp[0]$$dp[1]$$dp[2]$$dp[3]$
初始1000
处理完硬币 11111
处理完硬币 21122

答案 2，正确。

为什么？ 因为 $dp[j]$ 这个状态根本不足以定义子问题。真正的状态是二维的：$dp[k][j] =$ "只允许使用前 $k$ 种硬币，凑出 $j$ 的方案数"。外层枚举硬币时，那个 $k$ 维度被循环的进度隐式地表达了——处理完硬币 1 的那一行，就是 $k=1$ 的整行。而外层枚举金额时，$k$ 这一维消失了，$dp[j-1]$ 里混着"已经用过硬币 2"的方案，于是同一个组合被按不同顺序重复计入。

该记住的判断：一维滚动数组是二维状态的压缩表示，压缩掉的那一维由循环顺序承载。写一维 DP 时如果说不清"当前这一行对应哪个隐式维度的取值"，那就是状态设计出了问题，而不是循环写错了。同类陷阱在"最多交易两次的股票买卖"里也会出现：若状态只记"到第 $i$ 天的最大收益"而不记"已经交易几次"，算法会把所有上涨段全部吃掉——对输入 $[1,5,2,8,1,9]$ 会给出 $4+6+8=18$，而至多两次交易的真实上限是 $7 + 8 = 15$。

代价与争议

不是万灵药：DP 要求重叠子问题。如果子问题完全独立（如归并排序），分治已经是最优，DP 带来不了额外好处。

空间与时间的权衡：记忆化的代价是内存。$O(mn)$ 的 DP 表格在 $m, n$ 很大时可能需要几 GB 内存。实践中常用"滚动数组"优化，只保留几行而非整张表——但如上文 LIS 与背包两处所示，压缩掉的行往往正是回溯出具体方案所需的信息。只要值、还是要方案，这个问题必须在设计阶段就想清楚。

伪多项式时间：背包问题的 $O(nW)$ 看起来是多项式，但 $W$ 是物品重量的数值，而非输入规模的位数。如果物品重量可以达到 21002^{100}，$W$ 就是 21002^{100}，算法的真实时间是指数的。这类复杂度称为"伪多项式时间"，背包问题实际上是 NP 困难的。

"DP 是可以套模板的"这个说法有多可靠：教学上常把 DP 拆成"定义状态 → 写转移 → 定边界 → 定顺序"四步模板，实践中真正难的只有第一步，而第一步没有模板。上文硬币兑换的例子说明，同一份三行代码可以对应两个不同的问题；状态是否成立要靠"它是否唯一确定一个子问题"来检验，而这项检验只能靠对问题本身的理解，不能靠套用。

跨域连接

  • 控制论：最优控制有两条等价路线——变分法给出开环轨迹与伴随方程，Bellman 方程给出从状态到动作的反馈律。后者的连续极限是一个偏微分方程，状态维度一高就无法求解，"维度灾难"这个词正出自这里。选哪条路取决于扰动大不大：无扰动时开环够用，有扰动就必须有反馈，而反馈只能从这一侧得到。
  • 时间贴现：无限期决策之所以有唯一解，靠的是折扣因子小于一使 Bellman 算子成为压缩映射。这个参数既是经济假设也是数值条件：越接近一，压缩越弱、值迭代收敛越慢，而它同时刻画着决策者对未来的重视程度。调高它来"更看重长期"会同时把求解成本推高——这不是实现问题，是同一个参数的两副面孔。
  • 强化学习：值迭代与策略迭代就是在状态空间上填表，与经典动态规划没有区别。分岔点在于转移概率是否已知：知道就能直接算期望，不知道就只能靠采样估计，于是引入了方差与探索问题。所谓"无模型"方法，去掉的不是动态规划的骨架，而是那张已知的转移表。
  • 生命之树与系统发育：在给定的树上推断祖先状态，用的是自下而上的后序递推——每个节点的最优代价只依赖它的子树，这正是最优子结构。前提是树无环：一旦承认基因水平转移或杂交，演化关系成为网状图，子问题相互依赖，同一套递推立刻失效。这也是网状演化远难于树推断的算法根源。
  • 拉格朗日与哈密顿力学：费马原理说光走光程稳定的路径，而最短路径的任何一段也必然是那两点之间的最短路径——最优子结构在几何光学里是成立的，惠更斯作图法本质上就是逐层推进的动态规划。它的边界同样清楚：波长不可忽略时干涉让多条路径共同贡献，"唯一最优路径"这个前提消失，射线光学随之失效。

参考文献

  • Bellman, R. Dynamic Programming. Princeton University Press, 1957. （创始人之书）
  • Bellman, R. Eye of the Hurricane: An Autobiography. World Scientific, 1984.（"dynamic programming"命名经过与国防部长威尔逊一节）
  • Dreyfus, S. "Richard Bellman on the Birth of Dynamic Programming." Operations Research 50(1), 48–51 (2002).（对上述自传段落的引述与考订）
  • Cormen, T. et al. Introduction to Algorithms (CLRS). 3rd ed. 第15-16章. MIT Press, 2009.
  • Fredman, M. L. "On Computing the Length of Longest Increasing Subsequences." Discrete Mathematics 11(1), 29–35 (1975).（LIS 的 O(nlog⁡n)O(n\log n) 与比较次数下界）
  • Schensted, C. "Longest Increasing and Decreasing Subsequences." Canadian Journal of Mathematics 13, 179–191 (1961).（LIS 与 Young 表的对应）

延伸阅读

  • Skiena, S. The Algorithm Design Manual. 3rd ed. Springer, 2020. （第10章，DP 的工程实践视角）
  • Aldous, D. & Diaconis, P. "Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem." Bulletin of the AMS 36(4), 413–432 (1999).（同一个尾数组算法，被当成一种纸牌游戏来分析）
  • Bertsekas, D. Dynamic Programming and Optimal Control. 4th ed. Athena Scientific, 2017.（从控制论一侧看 Bellman 方程，与算法教材的视角互补）

正文中引用本条 · 10 · 其中 4 条来自其他领域

数学变分法拉马努金组合数学
经济学机会成本