🧠 第六部分：动态规划
竞赛编程中最强大也最需要训练的主题。掌握记忆化、递推、经典模型、折半枚举与数位计数，逐步跨过 USACO Silver 到 Gold 的门槛。
📚 8 章 · ⏱️ 预计 5-7 周 · 🎯 目标：USACO Silver → Gold
第六部分：动态规划
预计用时：4-6 周
动态规划不是背公式，而是把一个大问题拆成许多会重复出现的小问题。你需要学会定义状态、设计转移、处理边界，并判断什么时候 DP 不是最好的工具。本部分从最基础的一维 DP 开始，逐步过渡到背包、LIS、状压、区间、树形、折半搜索和数位 DP。
涵盖的主题
| 章节 | 主题 | 核心思想 | 目标层级 |
|---|---|---|---|
| 第 6.1 章 | DP 入门 | 记忆化、递推、DP 四步法 | Bronze/Silver |
| 第 6.2 章 | 经典 DP 问题 | LIS、背包、网格路径、方案数 | Silver |
| 第 6.3 章 | 进阶 DP 模式 | 状压 DP、区间 DP、树形 DP | Silver/Gold |
| 第 6.4 章 | 折半搜索 | 将 2^N 拆成两个 2^(N/2) 再合并 | Gold |
| 第 6.5 章 | 数位 DP | 按位填数，统计 [L, R] 内满足数字性质的数 | Gold |
| 第 6.6 章 | DP 优化 | 单调队列、斜率优化、决策单调性：削减转移冗余 | Gold/Platinum |
| 第 6.7 章 | 概率期望与计数 DP | 概率顺推、期望倒推、计数不重不漏 | Gold |
| 第 6.8 章 🥇 | 树形 DP 与换根 | 树上背包、换根 DP（二次扫描） | Gold |
学完本部分后能解决什么问题
完成第六部分后，你将能够挑战：
-
USACO Bronze：
- 简单计数问题（做某件事有多少种方法？）
- 基本优化问题（最小代价、最大收益）
-
USACO Silver：
- 最长递增子序列及其变体
- 0/1 背包、完全背包、二维费用背包
- 网格路径计数与最大价值路径
- 需要精确定义状态的一维/二维 DP
-
USACO Gold：
- 状压 DP、区间 DP、树形 DP
N≈40的指数枚举题：使用折半搜索把复杂度减半[L, R]内数字性质计数题：使用数位 DP 处理10^18级别范围- 多状态组合：数字和、余数、上一位、出现次数、上下界约束
需要掌握的关键 DP 模式
| 模式 | 章节 | 示例题目 | 关键提醒 |
|---|---|---|---|
| 一维 DP（顺序） | 6.1 | 斐波那契、爬楼梯 | 先写状态含义，再写转移 |
| 一维 DP（优化） | 6.1 | 硬币找零（最少硬币） | 最小值初始化为 INF |
| 一维 DP（计数） | 6.1 | 硬币找零（方案数） | 初始方案数通常是 dp[0]=1 |
| 二维 DP | 6.2 | 0/1 背包、网格路径 | 明确每一维代表什么 |
| LIS | 6.2 | O(N²) 与 O(N log N) LIS | tails 数组不是实际 LIS |
| 状压 DP | 6.3 | TSP、任务分配 | mask 表示集合状态 |
| 区间 DP | 6.3 | 矩阵链乘法、合并石子 | 按区间长度递增填表 |
| 树形 DP | 6.3 | 树上独立集 | 后序遍历先算子树 |
| 折半搜索 | 6.4 | 子集和、最大不超过 X 的子集和 | 2^40 不可做，两个 2^20 可做 |
| 数位 DP | 6.5 | 不含某数字、数字和、整除性 | tight 与 started 是核心 |
| 概率 DP | 6.7 | 转移概率累加 | 每个状态转移概率之和必须为 1 |
| 期望 DP | 6.7 | 绿蛙跳格、收集邮票 | 倒推：f[i] = 1 + Σp·f[后继] |
| 计数 DP | 6.7 | 数字组合、错排 | 分类不重不漏；每步取模 |
DP 思维方式
DP 不是死记公式，而是反复问四个问题：
- 状态是什么？ 描述一个子问题需要哪些信息？
- 转移是什么？ 当前状态能从哪些更小或更简单的状态得到？
- 初始条件是什么？ 哪些状态不用计算就知道答案？
- 计算顺序是什么？ 依赖必须先于被依赖者计算。
💡 核心思路： 如果暴力搜索中同一个子问题被反复计算，DP 就是把它缓存起来；如果暴力枚举太大但可以分成两半独立处理，折半搜索可能比 DP 更自然；如果范围大到不能枚举每个整数，但限制只和数字有关，数位 DP 往往是答案。
本部分学习建议
- 第 6.1 章不要跳。 你要真正理解“状态”和“转移”，而不是只记代码。
- 每个经典题至少写两遍。 一遍记忆化搜索，一遍递推填表；两种视角互相验证。
- 第 6.2 章重点练背包和 LIS。 它们是很多更难题的底层模型。
- 第 6.3 章开始进入 Silver/Gold。 状压、区间、树形 DP 都需要更强的状态设计能力。
- 第 6.4 章不是传统 DP，但和 DP 同样重要。 当你看到
N≤40和子集枚举时，应立即想到折半搜索。 - 第 6.5 章要画状态。 数位 DP 的
tight、started、pos最容易混，建议用小数字手工追踪。 - 所有 DP 都要检查边界。 空集、0、负数、
L=0、数组维度、INF溢出，都是常见陷阱。
⚠️ 警告： DP 第 1 号 bug：在最小化 DP 中使用
dp[w-c]前忘记检查dp[w-c] != INF。INF + 1会溢出！DP 第 2 号 bug：0/1 背包 vs 完全背包的循环顺序搞错了。倒序迭代 = 每件物品最多用一次；正序迭代 = 无限次使用。
Gold DP 第 1 号 bug：状态维度缺了一维。比如数位 DP 少了
tight或started，答案通常会在边界样例上错。