🧠 第六部分：动态规划
竞赛编程中最强大也最让人头疼的主题。掌握记忆化、递推以及 USACO Silver 的经典 DP 模式。
📚 3 章 · ⏱️ 预计 3-4 周 · 🎯 目标：达到 USACO Silver 水平
第六部分：动态规划
预计用时：3-4 周
动态规划是竞赛编程中最强大也最让人头疼的主题。一旦掌握，你就能解决暴力法看似不可能解决的问题。这部分值得你慢慢来——真的值得。
涵盖的主题
| 章节 | 主题 | 核心思想 |
|---|---|---|
| 第 6.1 章 | DP 入门 | 记忆化、递推、DP 四步法 |
| 第 6.2 章 | 经典 DP 问题 | LIS、0/1 背包、网格路径计数 |
| 第 6.3 章 | 进阶 DP 模式 | 状压 DP、区间 DP、树形 DP |
学完本部分后能解决什么问题
完成第六部分后，你将能够挑战：
-
USACO Bronze：
- 简单计数问题（做某件事有多少种方法？）
- 基本优化（做某件事的最小代价是多少？）
-
USACO Silver：
- 最长递增子序列（及其变体）
- 背包类资源分配
- 网格路径问题（最大价值路径、路径计数）
- 精心定义状态的一维 DP（牛蹄剪刀布等）
- 区间 DP 或树形 DP（第 6.3 章）
需要掌握的关键 DP 模式
| 模式 | 章节 | 示例题目 |
|---|---|---|
| 一维 DP（顺序） | 6.1 | 斐波那契、爬楼梯 |
| 一维 DP（优化） | 6.1 | 硬币找零（最少硬币） |
| 一维 DP（计数） | 6.1 | 硬币找零（方法数） |
| 二维 DP | 6.2 | 0/1 背包、网格路径 |
| LIS（O(N²)） | 6.2 | 最长递增子序列 |
| LIS（O(N log N)） | 6.2 | 用二分搜索加速 LIS |
| 状压 DP | 6.3 | TSP、任务分配问题 |
| 区间 DP | 6.3 | 矩阵链乘法 |
| 树形 DP | 6.3 | 树上独立集 |
前置条件
开始第六部分前，请确认你能做到：
- 编写递归函数并理解调用栈（第 2.3 章）
- 熟练使用二维向量（第 2.3 章）
- 理解二分搜索（第 3.3 章）——O(N log N) LIS 需要
- 能解决基础 BFS 题目（第 5.2 章）——DP 和 BFS 共享「状态空间探索」的直觉
DP 思维方式
DP 不是死记公式——而是问对问题：
- 「状态」是什么？ 描述一个子问题需要哪些信息？
- 「转移」是什么？ 更大状态的答案如何依赖更小状态？
- 「初始条件」是什么？ 最简单的子问题答案是什么？
- 填表的顺序是什么？ 依赖关系必须在被使用之前先计算。
💡 核心思路： 如果你发现自己在递归解法中多次写相同的计算，DP 就是解药。第一次计算时缓存结果，之后每次直接复用。
本部分学习建议
- 仔细学第 6.1 章。 不要在真正理解斐波那契 DP 之前急着学背包。DP 的「为什么」比「是什么」更重要。
- 对同一道题同时写记忆化和递推两种实现。 在两者之间转换能加深理解。
- 第 6.2 章的 LIS 有两种实现：O(N²)（易理解）和 O(N log N)（快速，大 N 时需要）。两种都要学。
- 第 6.3 章是 Silver/Gold 级别。 如果目标是 Bronze，可以先跳过第 6.3 章，之后再回来。
- 大多数 DP bug 来自错误的初始化。 最小代价问题初始化为
INF，不是 0；计数问题把初始条件初始化为 1，不是 0。
⚠️ 警告： DP 第 1 号 bug：在最小化 DP 中使用
dp[w-c]前忘记检查dp[w-c] != INF。INF + 1会溢出！DP 第 2 号 bug：0/1 背包 vs 完全背包的循环顺序搞错了。倒序迭代 = 每件物品最多用一次。正序迭代 = 无限次使用。