动态规划

环境：Windows 11 x64，GCC 13.1.0，g++ -std=c++17 -O2。本文所有 DP 实现都与暴力参照做过随机对拍。

一、DP 的三个要素，用一句话判定

1. 最优子结构：大问题的最优解包含子问题的最优解。
2. 重叠子问题：递归会反复算同样的子问题（否则直接分治）。
3. 无后效性：状态一旦确定，之后的决策不影响它。

实操上就是回答三个问题：状态怎么定义（dp[i] 到底表示”什么的最优”）→ 转移方程是什么 → 边界和计算顺序是什么。90% 的 DP bug 出在第一问，而不是第三问。

二、斐波那契：三种写法的实测差距

long long fib_naive(int n){ return n < 2 ? n : fib_naive(n-1) + fib_naive(n-2); }
long long fib_memo(int n, vector<long long> &m){ long long &r = m[n]; if (r != -1) return r; return r = fib_memo(n-1,m) + fib_memo(n-2,m); }
long long fib_iter(int n){ long long a=0,b=1; for(int i=2;i<=n;i++){ long long c=a+b; a=b; b=c; } return n?b:0; }

n=40  朴素递归 196.9 ms | 记忆化 0.014 ms | 迭代 0.00010 ms（值 102334155/102334155/102334155）

• 朴素递归是 O(2ⁿ)，比记忆化慢 14000 倍。
• 记忆化（自顶向下）比迭代（自底向上）还慢 140 倍——因为每次递归调用有函数开销、缓存不友好，且要维护 memo 数组。“加了记忆化就是 DP”没错，但它不是最快的写法。
• 迭代版只用两个变量，O(1) 空间，快到 0.0001ms。

顺带一个必须记住的边界：

迭代 n=900000（溢出后是垃圾值）0.4 ms，末值 -6134324049495168

long long 只能到 fib(92)，之后是有符号溢出 UB（本机表现为回绕成负数）。写 DP 时先问”值域会不会爆类型”，这是最常见的静默错误。

三、0/1 背包：一维滚动数组必须逆序

/* 二维：语义最清楚 */
dp[i][c] = max(dp[i-1][c], dp[i-1][c - w[i]] + v[i]);

/* 一维滚动：内层容量必须从大到小 */
for (int i = 0; i < n; i++)
    for (int c = W; c >= w[i]; c--)              /* ← 逆序 */
        dp[c] = max(dp[c], dp[c - w[i]] + v[i]);

为什么逆序：dp[c - w[i]] 必须是”没考虑第 i 件物品”时的值。逆序遍历保证 c - w[i] < c 还没被本轮更新；正序则会被本轮更新覆盖，等于”第 i 件物品可以选多次”——那是完全背包。

实测这个错误的隐蔽程度（300 组随机背包，n ≤ 14、W ≤ 60）：

300 组随机用例：暴力 == 二维 == 一维逆序：1
一维写成"正序"（那是完全背包）与 0/1 结果不同的用例占比：232/300

有 68 组（23%）正序和逆序结果相同——因为最优解里每件物品恰好只用一次。也就是说：你随手测几个用例，很可能是”对的”。这类 bug 只能靠”与暴力对拍 + 大量随机数据”抓。

性能与内存收益（N=2000、W=4000）：

二维 43.1 ms | 一维 5.5 ms（结果一致=1，内存从 62546 KB 降到 31 KB）

快 7.8 倍、内存省 2000 倍。快是因为二维那张表太大，每次访问都在缓存 miss；一维数组 31KB 能整个留在 L1 里。这是”空间优化顺带做了性能优化”的典型。

四、最长上升子序列：O(n²) 与 O(n log n)

/* O(n²)：dp[i] = 以 a[i] 结尾的 LIS 长度 */
for (i) for (j < i) if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);

/* O(n log n)：tails[k] = 长度为 k+1 的上升子序列的最小结尾值 */
for (int x : a) { auto it = lower_bound(tails, x); it == end ? push_back(x) : *it = x; }

500 组随机（含大量重复值）两种实现一致=1
n=300000：O(n log n) 13.7 ms（LIS 长度 1080）

两个易错点：

1. 严格上升用 lower_bound，非下降（允许相等）用 upper_bound。写反了在重复元素上就错——所以我的随机测试故意把值域压到 50，制造大量重复。
2. tails 数组最终不是真实的 LIS，它只是”各长度的最小结尾值”的集合，长度才是答案。要还原方案得额外记录前驱。

五、编辑距离：滚动数组 + 与暴力对拍

vector<int> prev(t.size()+1), cur(t.size()+1);
for (j) prev[j] = j;
for (i = 1..) { cur[0] = i;
    for (j = 1..) cur[j] = min({ prev[j] + 1,            /* 删 */
                                 cur[j-1] + 1,           /* 插 */
                                 prev[j-1] + (s[i-1] != t[j-1]) });  /* 替换/相等 */
    swap(prev, cur); }

200 组随机短串（字母表 3 种）DP 与暴力一致=1
2000×2000 滚动数组 9.7 ms（距离 1771），内存 15 KB

三个要点：

• DP 的”三行”（删/插/替换）顺序无所谓，但 min 里三项一个都不能少——少一项就退化成 LCS。
• 滚动数组只能滚一维（两行），因为 cur[j] 依赖 cur[j-1]（同一行）和 prev[j]、prev[j-1]。想压成一维必须小心保存 prev[j-1]（用一个临时变量），否则就错了。
• 对拍用的暴力递归是 O(3^(n+m))，所以只能测极短串（≤ 8 字符）+ 小字母表。这也是通用原则：参照实现要能覆盖边界，就要牺牲规模。

六、DP 的四类常见形态与状态定义

形态	状态定义套路	例子
线性	dp[i] = 前 i 个 / 以 i 结尾	LIS、最大子段和、打家劫舍
区间	dp[i][j] = 区间 [i,j] 的答案，按长度枚举	矩阵链乘、石子合并、回文
背包	dp[i][c] = 前 i 件、容量 c	0/1、完全、多重背包
状态压缩	dp[mask] = 已访问集合为 mask	旅行商、棋盘覆盖

两个高频陷阱：

1. “前 i 个”和”以 i 结尾”是两个不同的定义，转移完全不同。最大子段和必须用后者（dp[i] = max(a[i], dp[i-1] + a[i])），用前者做不出来。
2. 区间 DP 的枚举顺序必须保证子区间先算完：按 len 从 2 到 n 枚举，而不是按 i 从 0 到 n。写错时结果”看起来合理”但不对。

七、记忆化的递归深度会爆栈

第三节说过递归 DFS 在 10 万层崩溃。同理：自顶向下的记忆化 DP 深度 = 状态链长度。

（斐波那契 n=40 的记忆化递归深度 40，安全；但"线性 DP 写成递归"时 n=10 万就会崩）

判据：状态转移链长度可能超过几千，就用自底向上的迭代 + 显式循环。记忆化只适合”状态稀疏、不是每个都要算”的场景（如搜索剪枝、区间查询型 DP）。

八、这一节的自查清单

• 先写暴力递归（定义清楚状态），再加记忆化，最后才改迭代和滚动数组——顺序不要反
• 每一步改写都与上一种实现随机对拍，不是”看代码觉得对”
• 一维滚动的遍历方向是 DP 正确性的一部分：0/1 背包逆序、完全背包正序
• 检查值域：int 会不会溢出、long long 够不够（斐波那契 92 项就到顶）
• 严格 vs 非严格（lower_bound / upper_bound）要用含重复值的随机数据测
• 随机测试要专门包含：空、单元素、全相等、逆序、边界容量
• 空间优化常常同时是性能优化（大表 → 缓存 miss）
• 转移链可能很深就用迭代，别用记忆化递归
• 打印 DP 表人工核对前几行，是最快的定位方式

下一节讲贪心、分治与回溯：贪心正确性怎么证（交换论证）、回溯的剪枝手段、以及为什么”能贪的时候别 DP”。