动态规划

动态规划 (Dynamic Programming, DP) 是算法设计中最重要、最通用的技术之一

它不是一个具体的算法，而是一种类似于分治法的元技术，是一种算法设计范式

“Programming” 不是指编程，而是来自 Richard Bellman 提出该方法时使用的”表格化求解方法”的含义

DP vs 分治： - 分治：将问题分解为更小的子问题，递归求解 - DP：求解所有更小的子问题，但只复用最优子问题的解

核心要素： 1. 子问题的定义（状态） 2. 最优子结构性质 3. 子问题间的关系（递推关系/转移方程） 4. 自底向上计算最优解的值 5. 从计算信息中构造最优解

DAG 中的最短路径

有向无环图 (DAG) 不含有向环，节点可按拓扑序排列在一条直线上，所有边从左指向右

递推关系

\[ \text{dist}[v] = \min_{u: (u,v) \in E} \{\text{dist}[u] + l(u,v)\} \]

算法

初始化: dist[s] = 0, dist[v] = ∞ 对所有 v ≠ s
按拓扑序处理每个节点 v:
    对每条入边 (u, v):
        dist[v] = min(dist[v], dist[u] + l(u,v))

时间复杂度：\(O(V + E)\)（线性时间）

DP 的本质

算法求解了一组子问题 \(\{\text{dist}(u) : u \in V\}\)：从最小的子问题 \(\text{dist}(s) = 0\) 开始，按拓扑序逐步求解

在 DP 中，DAG 是隐式的——节点是子问题（状态），边是依赖关系（转移函数）

“Every DP is really just shortest (or longest) path in a DAG.”

最长递增子序列 (LIS)

给定序列 \(a_1, a_2, \ldots, a_n\)，找最长递增子序列

DP 思路

子问题（前缀 DP）：\(L(j)\) = 以 \(a_j\) 结尾的 LIS 长度 \[ L(j) = 1 + \max\{L(i) : i < j \text{ 且 } a_i < a_j\} \]

不存在这样的 \(i\) 则 \(L(j) = 1\)，最终答案 \(\max_j L(j)\)

DAG 模型

构建 DAG：节点 \(1, \ldots, n\)，若 \(i < j\) 且 \(a_i < a_j\) 则有边 \((i, j)\)

\(L(j)\) = DAG 中以 \(j\) 结尾的最长路径长度

时间 \(O(n^2)\)，空间 \(O(n)\)

注：存在 \(O(n \log n)\) 的更快算法（二分搜索+贪心），利用辅助数组 \(d[k]\) 表示长度为 \(k\) 的递增子序列的最小末尾元素

加权区间调度

\(n\) 个工作，每个有开始时间 \(s_j\)、结束时间 \(f_j\)、权重 \(v_j\)，两个工作兼容当且仅当时间不重叠

找互相兼容的工作子集使总权重最大

符号定义

按结束时间排序 \(f_1 \leq f_2 \leq \ldots \leq f_n\)

\(p(j)\) = 与工作 \(j\) 兼容的最大下标 \(i < j\)（结束时间最晚但不与 \(j\) 冲突的工作）

二元选择递推

子问题：\(\text{OPT}(j)\) = 仅考虑工作 \(1, \ldots, j\) 时的最优值

\[\text{OPT}(j) = \max\begin{cases} v_j + \text{OPT}(p(j)) & \text{选择工作 } j \\ \text{OPT}(j-1) & \text{不选择工作 } j \end{cases}\]

\(\text{OPT}(0) = 0\)

最优子结构：

选 \(j\)：收获 \(v_j\)，不能用 \(p(j)+1, \ldots, j-1\)（与 \(j\) 冲突），必须包含 \(1, \ldots, p(j)\) 的最优解
不选 \(j\)：必须包含 \(1, \ldots, j-1\) 的最优解

朴素递归的问题

1
2
3

Compute-Opt(j):
    if j = 0: return 0
    else: return max(vⱼ + Compute-Opt(p(j)), Compute-Opt(j-1))

由于重叠子问题，递归树呈指数增长

记忆化

M-Compute-Opt(j):
    if j = 0: return 0
    if M[j] 已计算: return M[j]
    M[j] = max(vⱼ + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
    return M[j]

自底向上 DP

1
2
3

M[0] = 0
for j = 1 to n:
    M[j] = max(vⱼ + M[p(j)], M[j-1])

时间复杂度

排序：\(O(n \log n)\)
计算 \(p(\cdot)\)：\(O(n \log n)\)（二分搜索）
DP 部分：\(O(n)\)
总时间 \(O(n \log n)\)

构造最优解

Find-Solution(j):
    if j = 0: return ∅
    if vⱼ + M[p(j)] ≥ M[j-1]:
        return {j} ∪ Find-Solution(p(j))
    else:
        return Find-Solution(j-1)

递归调用次数 \(\leq n\)，时间 \(O(n)\)

最长公共子序列 (LCS)

给定 \(x[1..m]\) 和 \(y[1..n]\)，找最长公共子序列

示例：\(x\): ABCBDAB，\(y\): BDCABA，LCS: BCBA（长度 4）

暴力做法：枚举 \(x\) 的 \(2^m\) 个子序列，每次检查 \(\Theta(n)\)，总时间 \(\Theta(n \cdot 2^m)\)

DP 递推

子问题：\(c[i, j]\) = \(x[1..i]\) 和 \(y[1..j]\) 的 LCS 长度

最终答案：\(c[m, n]\)

\[ c[i, j] = \begin{cases} 0 & i = 0 \text{ 或 } j = 0 \\ c[i-1, j-1] + 1 & x[i] = y[j] \\ \max(c[i-1, j], c[i, j-1]) & \text{否则} \end{cases} \]

点击查看正确性证明

若 \(x[i] = y[j]\)：

设 \(z[1..k]\) 为 \(x[1..i]\) 和 \(y[1..j]\) 的 LCS（\(c[i,j] = k\)）

断言：\(z[k] = x[i] = y[j]\)

反证：如果 \(z[k] \neq x[i]\)，那么可以将 \(x[i]\) 追加到 \(z\) 后面，得到更长的公共子序列，矛盾

因此 \(z[1..k-1]\) 是 \(x[1..i-1]\) 和 \(y[1..j-1]\) 的公共子序列

断言：\(z[1..k-1]\) 是 \(x[1..i-1]\) 和 \(y[1..j-1]\) 的最长公共子序列

反证：若存在更长的 \(w\)，则 \(\langle w, x[i] \rangle\) 比 \(z\) 更长，矛盾

因此 \(c[i-1, j-1] = k - 1\)，即 \(c[i,j] = c[i-1, j-1] + 1\)

DP 算法

LCS-Length(X, Y):
    m ← length[X]
    n ← length[Y]
    for i ← 1 to m: c[i, 0] ← 0
    for j ← 0 to n: c[0, j] ← 0
    for i ← 1 to m:
        for j ← 1 to n:
            if xᵢ = yⱼ:
                c[i, j] ← c[i-1, j-1] + 1
                b[i, j] ← "↖"
            else if c[i-1, j] ≥ c[i, j-1]:
                c[i, j] ← c[i-1, j]
                b[i, j] ← "↑"
            else:
                c[i, j] ← c[i, j-1]
                b[i, j] ← "←"
    return c and b

详细示例

\(X = \langle A, B, C, B \rangle\)，\(Y = \langle B, D, C, A, B \rangle\)

    j:  0   1(B) 2(D) 3(C) 4(A) 5(B)
i
0       0   0    0    0    0    0
1(A)    0   0    0    0    1    1
2(B)    0   1    1    1    1    2
3(C)    0   1    1    2    2    2
4(B)    0   1    1    2    2    3

LCS 长度 = \(c[4, 5] = 3\)

回溯构造 LCS

Print-LCS(b, X, i, j):
    if i = 0 or j = 0: return
    if b[i, j] = "↖":
        Print-LCS(b, X, i-1, j-1)
        print xᵢ
    elseif b[i, j] = "↑":
        Print-LCS(b, X, i-1, j)
    else:
        Print-LCS(b, X, i, j-1)

从 \((4, 5)\) 回溯：\(B, C, B\) → LCS = “BCB”

时间 \(O(mn)\)，空间 \(O(mn)\)（可优化到 \(O(\min(m,n))\)，只保留上一行）

LCS 的 DAG 表示

(0,0) → (0,1) → ... → (0,n)
  ↓       ↓              ↓
(1,0) → (1,1) → ... → (1,n)
  ↓       ↓              ↓
 ...     ...            ...
  ↓       ↓              ↓
(m,0) → (m,1) → ... → (m,n)

水平边：不选 \(y[j]\)；垂直边：不选 \(x[i]\)；对角边（\(x[i] = y[j]\)）：匹配

LCS = 从 \((0,0)\) 到 \((m,n)\) 的最长路径（对角边权重 1，其他 0）

背包问题

0-1 背包：\(n\) 个物品，整数权重 \(s_i\)，价值 \(v_i\)，背包容量 \(W\)，每个物品要么放入要么不放

DP 递推

子问题：\(V(k, B)\) = 用物品 \(\{1, \ldots, k\}\)、容量 \(B\) 时的最大价值

\[ V(k, B) = \begin{cases} 0 & k = 0 \\ V(k-1, B) & s_k > B \text{（放不下）} \\ \max\{v_k + V(k-1, B - s_k), V(k-1, B)\} & \text{否则} \end{cases} \]

最终答案 \(V(n, W)\)

实现

初始化 arr[i][j] 全部为 "empty"

V(k, B):
    if k == 0: return 0
    if arr[k][B] != empty: return arr[k][B]
    if sₖ > B:
        result = V(k-1, B)
    else:
        result = max{vₖ + V(k-1, B - sₖ), V(k-1, B)}
    arr[k][B] = result
    return result

复杂度

时间 \(O(nW)\)，空间 \(O(nW)\)

伪多项式时间：\(W\) 的编码长度为 \(\log W\)，因此 \(O(nW) = O(n \cdot 2^{\log W})\) 是输入规模的指数函数

0-1 背包是 NP 难的，DP 给出了 \(W\) 不太大时非常实用的算法

0-1 背包 vs 分数背包

特性	0-1 背包	分数背包
物品可分割？	否	是
算法	DP, \(O(nW)\)	贪心, \(O(n\log n)\)
贪心可解？	否	是
NP-hard？	是	否

反例说明 0-1 背包不能贪心：\(A\)(10kg, 60), \(B\)(20kg, 100), \(C\)(30kg, 120), 容量 50

贪心（按价值/重量比）选 \(A+B\)，总价值 160；最优选 \(B+C\)，总价值 220

矩阵链乘法

多个矩阵相乘时，加括号方式不同，计算代价差异巨大

示例

\(A_1(10 \times 100)\)，\(A_2(100 \times 5)\)，\(A_3(5 \times 50)\)：

\((A_1 A_2) A_3 = 10 \times 100 \times 5 + 10 \times 5 \times 50 = 7500\)
\(A_1 (A_2 A_3) = 100 \times 5 \times 50 + 10 \times 100 \times 50 = 75000\)

差了 10 倍！

暴力

加括号方式数 = Catalan 数 \(C_{n-1} = \frac{1}{n}\binom{2(n-1)}{n-1} = \Omega(\frac{4^n}{n^{3/2}})\)，指数时间

最优子结构

最后一次乘法在位置 \(k\)：\((A_1 \cdots A_k)(A_{k+1} \cdots A_n)\)

左右两部分的加括号方式也必须是最优的（剪切-粘贴论证）

DP 递推

子问题：\(m[i, j]\) = 计算 \(A_i \cdots A_j\) 的最少标量乘法次数

\[ m[i, j] = \begin{cases} 0 & i = j \\ \min_{i \leq k < j} \{m[i, k] + m[k+1, j] + p_{i-1} p_k p_j\} & i < j \end{cases} \]

\(A_i\) 的维度为 \(p_{i-1} \times p_i\)

算法

MATRIX-CHAIN-ORDER(p):
    n ← length[p] - 1
    for i ← 1 to n: m[i, i] ← 0
    for l ← 2 to n:                    // l = 链的长度
        for i ← 1 to n - l + 1:
            j ← i + l - 1
            m[i, j] ← ∞
            for k ← i to j - 1:
                q ← m[i, k] + m[k+1, j] + pᵢ₋₁ · pₖ · pⱼ
                if q < m[i, j]:
                    m[i, j] ← q
                    s[i, j] ← k
    return m, s

时间 \(O(n^3)\)，空间 \(O(n^2)\)，区间 DP 的经典例子

最优二叉搜索树

不同关键字搜索频率不同，目标是使加权内部路径长度 WIPL 最小

\[ \text{WIPL} = \sum_{i=1}^{n} f_i \cdot d_i \]

\(f_i\) 是搜索频率，\(d_i\) 是深度（根为 1）

示例

\(A:4, B:2, C:1, D:3, E:5, F:2, G:1\)

按频率递减插入（先 \(E\)，再 \(A\)，再 \(D\)…）得到 WIPL = 42

最优 BST 得到 WIPL = 41，既将高频关键字靠近根，又保持树的合理平衡

DP

对每个 \(k\) 将 \(K_k\) 作为根：

\[ \text{WIPL}(i, j) = \min_{k} \left\{\text{WIPL}_L + \text{WIPL}_R + \sum_{t=i}^{i+j} f_t\right\} \]

最后一项因为选择根后所有其他节点深度增加 1

时间 \(O(n^3)\)（可用 Knuth 优化到 \(O(n^2)\)）

树上的加权独立集

输入：带权无向图 \(G = (V, E, W)\)

输出：独立集 \(S\)（没有相邻顶点），最大化 \(\sum_{v \in S} w_v\)

一般图上 NP 难，但在树上可以 DP 多项式时间求解

树 DP

以某个节点 \(r\) 为根，\(C(u)\) 为 \(u\) 的子节点集合

\[ \text{MIS}(u) = \max \begin{cases} \sum_{v \in C(u)} \text{MIS}(v) & \text{不选 } u \\ w_u + \sum_{v \in C(C(u))} \text{MIS}(v) & \text{选 } u\text{，子节点不能选，跳到孙节点} \end{cases} \]

时间 \(O(n)\)

旅行商问题 (TSP)

完全图，经过每个顶点恰好一次的最短环游

暴力 \(O(n!)\)，DP \(O(n^2 \cdot 2^n)\)

子问题设计

考虑从城市 1 出发的部分旅行，需知道当前所在城市 \(j\) 和已访问集合 \(S\)

子问题：对 \(S \subseteq \{1, \ldots, n\}\)（含城市 1）和 \(j \in S\)

\[C(S, j) = \text{从 1 出发，恰好访问 } S \text{ 中每个城市一次，到达 } j \text{ 的最短路径}\]

递推关系

\[ C(S, j) = \min_{i \in S \setminus \{j\}} \{C(S \setminus \{j\}, i) + d_{ij}\} \]

\(C(\{1\}, 1) = 0\)

最终答案：\(\min_{j \neq 1} \{C(\{1, \ldots, n\}, j) + d_{j1}\}\)

复杂度

子问题数：\(2^n \cdot n\)
每个 \(O(n)\)
总时间 \(O(n^2 \cdot 2^n)\)，空间 \(O(n \cdot 2^n)\)

\(n\)	\(n!\)	\(n^2 2^n\)
10	3,628,800	102,400
15	\(1.3 \times 10^{12}\)	7,372,800
20	\(2.4 \times 10^{18}\)	419,430,400
25	\(1.6 \times 10^{25}\)	\(2.1 \times 10^{10}\)

子集 DP 经典例子。Held-Karp 算法（1962），60+ 年来仍是精确求解 TSP 的最佳已知算法

区间 DP：最少插入回文

给定 \(x = x_1 \ldots x_n\)，找需要插入的最少字符数使其成为回文

例：\(x = \text{Ab3bd}\) → “dAb3bAd” 或 “Adb3bdA”，需要插入 2 个字符

子问题：\(D_{ij}\) = 使 \(x_i \ldots x_j\) 成为回文的最少插入数

\[ D_{ij} = \begin{cases} 0 & i \geq j \\ D_{i+1, j-1} & x_i = x_j \\ 1 + \min(D_{i+1, j}, D_{i, j-1}) & x_i \neq x_j \end{cases} \]

直觉：\(x_i = x_j\) 时首尾相同无需插入；\(x_i \neq x_j\) 时，要么在左端插入 \(x_j\) 的副本，要么在右端插入 \(x_i\) 的副本

填表顺序：按 \(j - i\) 递增，时间 \(O(n^2)\)

DP 的分类与设计模式

常见 DP 类型

类型	子问题参数	典型问题
前缀 DP	前 \(i\) 个元素	LIS, 加权区间调度
双前缀 DP	\(x[1..i]\) 和 \(y[1..j]\)	LCS, 编辑距离
背包 DP	前 \(k\) 个物品、容量 \(B\)	0-1 背包
区间 DP	区间 \([i, j]\)	矩阵链乘法, 最优BST, 回文
树形 DP	以 \(u\) 为根的子树	树上独立集
子集 DP	子集 \(S\)	TSP
DAG DP	DAG 中的节点	最短路径

DP 设计步骤

定义子问题（状态）
写出递推关系（转移方程）
确定基本情况
确定计算顺序（拓扑序）
分析复杂度：子问题数 \(\times\) 每个子问题时间
（可选）回溯构造解

最优子结构与重叠子问题

最优子结构：问题的最优解包含子问题的最优解

“剪切-粘贴”论证：假设子问题解不最优，替换后得到更好全局解，矛盾

反例：最长简单路径不具有最优子结构。\(u \to w\) 的最长简单路径和 \(w \to v\) 的最长简单路径可能共享顶点，无法拼接。对比最短路径：子路径不会”绕远路”

重叠子问题：递归反复求解相同子问题，这是 DP 区别于分治的关键。分治的子问题不重叠（如归并排序），不需记忆化

贪心 vs DP：贪心也利用最优子结构，但不求解所有子问题——每步做当前最优选择。DP 比较所有可能选择确定全局最优

习题

习题 15.4-3：LCS 的记忆化版本

MEMOIZED-LCS-LENGTH(X, Y):
    初始化 c[0..m][0..n] 为 -1
    return LOOKUP-LCS(X, Y, m, n, c)

LOOKUP-LCS(X, Y, i, j, c):
    if c[i][j] > -1: return c[i][j]
    if i == 0 or j == 0: c[i][j] ← 0
    else if X[i] == Y[j]:
        c[i][j] ← LOOKUP-LCS(X, Y, i-1, j-1, c) + 1
    else:
        c[i][j] ← max(LOOKUP-LCS(X, Y, i-1, j, c),
                       LOOKUP-LCS(X, Y, i, j-1, c))
    return c[i][j]

\((m+1)(n+1)\) 个子问题，每个最多计算一次，总时间 \(O(mn)\)

优势：只计算实际需要的子问题，两个序列少量匹配时实际计算远少于 \(mn\)

习题 15.4-4：LCS 空间优化

\(c[i, j]\) 只依赖 \(c[i-1, j-1]\)、\(c[i-1, j]\) 和 \(c[i, j-1]\)，只需上一行和当前行

SPACE-EFFICIENT-LCS-LENGTH(X, Y):
    确保 m ≥ n
    prev[0..n] ← 全 0
    for i ← 1 to m:
        curr[0] ← 0
        for j ← 1 to n:
            if X[i] == Y[j]:
                curr[j] ← prev[j-1] + 1
            else:
                curr[j] ← max(prev[j], curr[j-1])
        swap prev, curr
    return prev[n]

空间 \(2\min(m, n) + O(1)\)。只能算长度，无法回溯。若需同时省空间又能构造 LCS，需 Hirschberg 算法

问题 15-2：最长回文子序列

\(x\) 的最长回文子序列 = \(x\) 与 \(x\) 的逆序 \(x^R\) 的 LCS

正确性：\(x\) 的任何回文子序列既是 \(x\) 的子序列也是 \(x^R\) 的子序列

直接 DP：\(P[i, j] = x[i..j]\) 的最长回文子序列长度

\[ P[i, j] = \begin{cases} 1 & i = j \\ 2 & i+1 = j, x[i] = x[j] \\ P[i+1, j-1] + 2 & x[i] = x[j] \\ \max(P[i+1, j], P[i, j-1]) & \text{否则} \end{cases} \]

时间 \(O(n^2)\)

问题 15-5：编辑距离

\(c[i, j]\) = 将 \(x[1..i]\) 变换为 \(y[1..j]\) 的最小代价

\[ c[i, j] = \begin{cases} j \cdot \text{cost}_{\text{ins}} & i = 0 \\ i \cdot \text{cost}_{\text{del}} & j = 0 \\ \min \begin{cases} c[i-1, j-1] + \text{cost}_{\text{copy}} & x[i] = y[j] \\ c[i-1, j-1] + \text{cost}_{\text{replace}} \\ c[i-1, j] + \text{cost}_{\text{delete}} \\ c[i, j-1] + \text{cost}_{\text{insert}} \end{cases} & \text{否则} \end{cases} \]

时间 \(O(mn)\)

习题 15.3-3：为什么记忆化不能加速归并排序

归并排序的子问题是”对 \(A[\ell..r]\) 排序”，没有重叠，每个子数组在递归树中只出现一次

两半不重叠，不存在同一子问题被多次求解

DP 的核心前提：只有重叠子问题时，记忆化才能加速

自顶向下 vs 自底向上

特征	自顶向下（记忆化）	自底向上（迭代）
实现	递归 + 缓存	循环填表
子问题求解	只求解需要的	求解所有
递归开销	有	无
代码风格	更自然	需确定填表顺序

自顶向下适合部分子问题被需要时，自底向上通常更快且某些空间优化只能在此时实现

空间优化

LCS：\(O(mn) \to O(\min(m,n))\)（只需上一行）
背包：\(O(nW) \to O(W)\)
矩阵链乘法：无法直接优化

附录

Catalan 数

\[ C_n = \frac{1}{n+1}\binom{2n}{n} = \Omega(4^n / n^{3/2}) \]

出现在：\(n\) 个节点的不同二叉树数、\(n\) 对括号的合法排列数、矩阵链加括号数

位掩码表示子集

检查第 \(i\) 位：S & (1 << i)
设置第 \(i\) 位：S | (1 << i)
清除第 \(i\) 位：S & ~(1 << i)
遍历所有子集：for S in range(1 << n)
遍历 \(S\) 的子集 \(T\)：T = S; while T > 0: T = (T-1) & S

DP 优化技术

优化	适用条件	效果
滚动数组	只依赖上一行	空间降一维
Knuth 优化	决策点单调	区间 DP \(O(n^3) \to O(n^2)\)
四边形不等式	代价函数满足四边形不等式	同上
斜率优化	转移有线性项	\(O(n^2) \to O(n \log n)\) 或 \(O(n)\)
数据结构优化	转移需区间最值	线段树/单调队列加速

记忆化模式

memo = {}

def dp(state):
    if state in memo:
        return memo[state]
    if is_base_case(state):
        result = base_value(state)
    else:
        result = transition(state)
    memo[state] = result
    return result

TSP 的近似算法

精确求解是指数级的，实际中常用近似：

算法	近似比	时间	条件
最近邻	无保证	\(O(n^2)\)	无
Christofides (1976)	3/2	\(O(n^3)\)	三角不等式
LKH 启发式	实际接近最优	多项式	无

Christofides 的 \(3/2\) 近似比保持了 44 年，直到 Karlin, Klein, Gharan (2020) 改进到 \(3/2 - 10^{-36}\)

(´-ω-｀)

DAG 中的最短路径

递推关系

算法

DP 的本质

最长递增子序列 (LIS)

DP 思路

DAG 模型

加权区间调度

符号定义

二元选择递推

朴素递归的问题

记忆化

自底向上 DP

时间复杂度

构造最优解

最长公共子序列 (LCS)

DP 递推

DP 算法

详细示例

回溯构造 LCS

LCS 的 DAG 表示

背包问题

DP 递推

实现

复杂度

0-1 背包 vs 分数背包

矩阵链乘法

示例

暴力

最优子结构

DP 递推

算法

最优二叉搜索树

示例

DP

树上的加权独立集

树 DP

旅行商问题 (TSP)

子问题设计

递推关系

复杂度

区间 DP：最少插入回文

DP 的分类与设计模式

常见 DP 类型

DP 设计步骤

最优子结构与重叠子问题

习题

习题 15.4-3：LCS 的记忆化版本

习题 15.4-4：LCS 空间优化

问题 15-2：最长回文子序列

问题 15-5：编辑距离

习题 15.3-3：为什么记忆化不能加速归并排序

自顶向下 vs 自底向上

空间优化

附录

Catalan 数

位掩码表示子集

DP 优化技术

记忆化模式

TSP 的近似算法

动态规划

同分类文章