第 5 章 · 01 动态规划（对应 docs/dp/）

第 5 章 · 01 动态规划（对应 docs/dp/）

本节定位：对应 OI Wiki docs/dp/（共 22 篇）。难度：进阶。前置依赖：算法基础（第 2 章枚举/递归/二分）、数据结构（第 3 章基础结构）。本节是非难点导读节，把扁平的 22 篇按"三要素 → 经典模型"串成学习顺序，具体推导回 Wiki 页面看。

⚠️ 注意：DP 是竞赛的"半壁江山"，NOIP/CSP 的压轴常考，省选也必出现。本节只做导航，不重写 Wiki。每个模型都标注对应 docs/dp/ 的具体页面，务必点进去精读代码模板。

知识地图

OI Wiki docs/dp/ 是按模型分文件存放的，新读者容易"不知从哪开始"。这里把它们按学习先后重排。

第一站：DP 三要素（一切模型的基石）

所有 DP 题都围绕三件事，先把这三个抽象概念扎根，后面每个模型都只是"换一种填法"。对应 Wiki 总览页 docs/dp/index.md。

• 状态设计：用若干变量描述"子问题"，如 f[i][j] 表示"前 i 个物品、容量 j 的最优解"。状态设计决定了空间复杂度，也决定了能否想到转移。
• 状态转移方程：从已知状态推出新状态，如 f[i][j] = max(f[i-1][j], f[i-1][j-w]+v)。转移方程是 DP 的"灵魂"。
• 边界与答案：初始值（f[0][0]=0）和最终答案在哪个状态。边界错了，转移再对也全错。

两种实现方式：递推（用循环填表）和记忆化搜索（递归 + 缓存，见本节第八站）。两者等价，前者快、后者直观。

💡 学习提示：拿到任何 DP 题，先别想代码，先用一句话写清"状态表示什么"，再画转移方程。这两步想清楚，代码自然出来。90% 的 DP 不会做，卡在"状态设计"而不是"代码"。

第二站：背包 DP（docs/dp/knapsack.md）

入门第一课，必会。三种背包只差一个"物品数量"的约束：

• 0-1 背包：每个物品取或不取，f[j] = max(f[j], f[j-w[i]] + v[i])，逆序枚举 j。
• 完全背包：物品无限个，同样的方程但顺序枚举 j。
• 多重背包：物品有数量上限，用二进制分组优化到 O(nW log m)。

⚠️ 注意：0-1 背包为什么必须逆序？因为"每个物品只用一次"，顺序枚举会让同一物品被重复拿。这是完全背包和 0-1 背包的唯一差别，理解了就不会再背混。

第三站：线性 DP

• 最长递增子序列 LIS（docs/dp/basic/lis.md）：朴素 O(n²)，f[i] 表示以 i 结尾的最长递增子序列长度。二分优化到 O(n log n)——维护一个"长度为 k 的递增子序列的最小尾元素"数组，每次二分插入。O(n log n) 版本是面试与竞赛双高频，务必会写 lower_bound 那一版。
• 最长公共子序列 LCS（docs/dp/basic/lcs.md）：f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1]+1)，经典二维 DP。当字符集小时有优化到 O(n log n) 的技巧（转为 LIS）。

第四站：区间 DP（docs/dp/interval.md）

典型题石子合并：把相邻两堆合并，问最小代价。状态 f[l][r] 表示合并区间 [l,r] 的最小代价，枚举断点 k：f[l][r] = min(f[l][k] + f[k+1][r]) + sum(l,r)，复杂度 O(n³)。

• 关键是枚举顺序：必须"先小区间后大区间"（按区间长度 len 从小到大枚举），否则大区间依赖的状态还没算出来。
• 进阶有四边形不等式优化到 O(n²)，但属于省选级，初学先掌握 O(n³)。

第五站：树形 DP（docs/dp/tree.md）

在树上做 DP，典型题没有上司的舞会（选了父亲就不能选孩子）。状态分"选/不选当前节点"两维，后序遍历转移：

f[u][1] = v[u] + Σ f[child][0]            // 选 u，孩子都不能选
f[u][0] = Σ max(f[child][0], f[child][1]) // 不选 u，孩子可选可不选
​

也可用于求树的直径（每个节点维护"向下最长链/次长链"，过该点的最长路径 = 最长 + 次长），以及树的最大独立集等问题。

第六站：数位 DP（docs/dp/number.md）

统计"1 到 n 中数字 x 出现了多少次""1 到 n 中满足某条件的数有几个"这类问题。按"从高位到低位逐位填，记录是否贴上界"的状态，用记忆化搜索写最自然。典型题如"不含 4 和 62 的数"。核心是 dfs(pos, limit, ...) 的参数设计。

第七站：状压 DP（docs/dp/state.md）

状态空间小（n ≤ 20）时，用二进制整数压缩状态。典型题旅行商 TSP：f[S][i] 表示已访问集合 S、当前在点 i 的最短路径，转移枚举下一个点 j：f[S|1<<j][j] = min(f[S][i] + w[i][j])。位运算 S | (1<<j)、S & (1<<j) 是核心操作。

第八站：记忆化搜索（docs/dp/memo.md）

递归 + 缓存 = DP。本质和递推 DP 等价，但写法更直观，特别适合"状态转移不规律"或"有效状态稀疏"的题（如滑雪、数字三角形、数位 DP）。优点是只计算真正用到的状态，缺点是有递归常数。学会它很多题能直接 AC，是 DP 的"万能写法"。

其他进阶模型（点名）

docs/dp/ 还有概率期望 DP（docs/dp/probability.md，期望倒推）、背包变形（docs/dp/opt.md，单调队列优化多重背包）、DAG 上 DP 等，属于进阶内容，建议基础扎实后再学。

DP 模型与典型题对照

学习建议

1. 必会清单：背包（0-1/完全）、LIS（O(n log n) 版）、LCS。这三个是任何 DP 题的"肌肉记忆"，必须能 5 分钟内默写。
2. 画状态转移图：学新模型时，在纸上画 2×2 的小例子，标出状态和转移箭头，比看十遍代码都管用。
3. 先想状态再写代码：90% 的 DP 错误是"状态设计错了"，不是代码 bug。卡住时退回去重想"我的状态到底表示什么"。
4. 读 Wiki 顺序：knapsack.md → basic/lis.md → basic/lcs.md → interval.md → tree.md → state.md → memo.md，每个文件都有完整模板代码，建议亲手敲一遍。
5. 按难度递进刷题：背包（黄）→ LIS/LCS（绿）→ 区间 DP（绿蓝）→ 树形/数位（蓝）→ 状压（蓝紫）。不要跳级，每一档稳定 AC 再下一档。

💡 学习提示：DP 的"难度"不在某个模型，而在"把陌生题归约到已知模型"。多刷分类题（洛谷 DP 专题），培养"看到题就反应这是什么 DP"的直觉。

本节要点

• DP 三要素：状态、转移、边界，是所有模型的统一框架。
• 背包（0-1/完全/多重）和 LIS/LCS 是必会基础。
• 区间 DP（石子合并）、树形 DP（舞会）、数位 DP、状压 DP（TSP）是四大经典模型。
• 记忆化搜索是"递归版 DP"，与递推等价。
• 本节是导读，深入推导见 docs/dp/ 各页面；难点 SAM 在第 5 章 · 03 节。