昨晚你也许已经做过这样的题：明明题目在讲链表、路径或选择，你却用数组把所有可能结果记录下来，最后仍然做对了。动态规划里也会反复出现这种“表示转换”：题面展示的是选择树，代码里保存的却是数组；题面看起来是网格，真正决定算法的却是状态之间的依赖边。
这一章不从一张 dp 模板表开始。我们先追问：暴力搜索到底重复计算了什么？为了让未来不再关心过去的细节，一个状态至少要保存哪些信息？
如果这两个问题答清楚，记忆化搜索、递推表、滚动数组和背包循环方向就不再是彼此孤立的技巧。
学习目标
完成本章的核心部分后，你应该能够：
- 从暴力递归的参数中识别重复子问题；
- 用一句可检验的自然语言定义状态，而不是只写“
dp[i]表示答案”； - 从“最后一步”或“当前决策”推出转移方程；
- 分别确定边界、不可达值、计算顺序和最终答案位置；
- 在记忆化搜索与自底向上递推之间双向翻译；
- 判断一维压缩时哪些旧状态还能读、哪些已经被覆盖；
- 区分可行性、最值与计数 DP，并识别组合数和排列数的循环差异；
- 用正确性证明、小规模暴力和最小反例验证自己的状态设计。
先判断：这是贪心、搜索，还是动态规划？
方法不是由题目中的名词决定的。看到“最小”不一定是贪心，看到“所有方案”也不一定只能搜索。
| 观察 | 更值得先尝试的方法 | 仍需确认的问题 |
|---|---|---|
| 每一步存在可证明的安全局部选择 | 贪心 | 局部选择会不会排除某个全局最优解？ |
| 状态空间不大，且需要枚举具体方案 | 搜索/回溯 | 能否剪枝？同一子问题是否反复出现？ |
| 同一子问题重复出现，答案可由更小子问题组合 | 动态规划 | 状态信息是否足够？依赖是否无环？ |
| 边权满足特定结构、需要最短路径 | 图算法 | 所谓“状态”是否其实是图结点？ |
DEF定义 · 动态规划
动态规划把一个问题分解为有限个可复用的状态，按照状态依赖的合法顺序，只求解每个状态一次，再由这些状态组合出原问题的答案。
它是一种组织子问题和计算顺序的方法，不是“必须使用二维数组”的语法模板。
IDEA直觉 · 搜索树折叠成状态图
暴力搜索把“每条选择过程”当成一条独立路径。动态规划发现：不同路径可能到达完全相同的剩余问题。把这些相同结点合并，搜索树就折叠成一个更小的状态有向无环图。
完整案例 1 · 一般找零：局部最优为什么会失效
1. 题意与复杂度信号
给定硬币面额和目标金额，每种硬币可以使用任意次，求凑出目标金额所需的最少硬币数。若面额是 {1, 3, 4}，目标是 6。
如果只看当前余额，最诱人的规则是“每次拿不超过余额的最大硬币”。它会得到：
6 -> 拿 4 -> 余额 2 -> 拿 1 -> 余额 1 -> 拿 1
共 3 枚但最优方案是 3 + 3，只需 2 枚。
ANTI反例 · 贪心选择不可撤回
“先拿最大面额”在标准人民币等特定面额体系中可能有效，却不是一般定理。面额 {1,3,4}、金额 6 是最小而清楚的反例：第一次拿 4 已经排除了最优解 3+3。
这也连接了上一章的贪心与动态规划边界：没有安全选择证明，就不能因为规则直观而称它正确。
2. 从暴力选择到子问题
设 dfs(x) 表示凑出金额 x 的最少硬币数。最后放入的硬币可能是任意 c，于是去掉它之后留下子问题 dfs(x-c)：
暴力递归会多次遇到相同余额。例如从 6 先拿 3，或先拿 1 再拿 1 再拿 3，都可能继续询问“凑出金额 3 最少要几枚”。递归路径不同，剩余问题却相同。
3. 状态设计卡
| 问题 | 本例答案 |
|---|---|
| 阶段/规模 | 当前需要凑出的金额 x |
| 状态语义 | f[x]：恰好凑出 x 的最少硬币数 |
| 最后一步 | 选择最后一枚硬币 c |
| 转移 | f[x] = min(f[x], f[x-c] + 1) |
| 边界 | f[0]=0；其余初始为不可达 INF |
| 计算顺序 | 金额从小到大，因为 x-c < x |
| 答案位置 | f[target]；仍为 INF 则无解 |
4. 正确性
THM定理 · 找零递推的正确性
若 f[x] 取所有可作为最后一枚的硬币 c 对应的 f[x-c]+1 的最小值，则 f[x] 等于恰好凑出 x 的最少硬币数。
PROOF证明
任取一个凑出 x 的最优方案，设最后一枚硬币为 c。删去它后，剩余硬币必须凑出 x-c；若这部分不是 x-c 的最优方案，就能替换成更短方案，使原方案更短，产生矛盾。因此最优值一定出现在某个 f[x-c]+1 中。
反过来，只要 f[x-c] 可达，在其对应方案末尾添加硬币 c 就得到一个合法的 x 方案。所以转移不会产生虚假答案。上下界相同，递推正确。
5. C++17 实现
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
int minCoins(const std::vector<int>& coins, int target) {
const int INF = std::numeric_limits<int>::max() / 4;
std::vector<int> f(target + 1, INF);
f[0] = 0;
for (int x = 1; x <= target; ++x) {
for (int coin : coins) {
if (coin <= x && f[x - coin] != INF) {
f[x] = std::min(f[x], f[x - coin] + 1);
}
}
}
return f[target] == INF ? -1 : f[target];
}
int main() {
std::cout << minCoins({1, 3, 4}, 6) << '\n';
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
O(·)复杂度 · 一般找零
共有 target+1 个金额状态，每个状态尝试 m 种硬币，时间复杂度为
WARN易错点 · 不可达不是零
若把所有 f[x] 初始化为 0，程序会把“尚未找到方案”误当成“无需硬币”。最小化问题常用足够大的 INF 表示不可达，而且相加前要确认前驱不是 INF，避免溢出和伪答案。
迁移问题： 若题目改为“有多少种组合”，状态空间仍是金额，但状态值的代数意义、初值和枚举顺序都会改变。我们会在背包动态规划中正面对比。
完整案例 2 · 数字三角形：把指数搜索折叠成表
1. 题意与暴力搜索
从三角形顶端出发，每一步只能走到下一行的正下方或右下方，求到达底层的最大路径和。例如：
2
3 4
6 5 7
4 1 8 3每一层都有两个选择，高度为 n 时最多有
但从顶端走到 (i,j) 的不同路径，接下来面对的是同一个“从 (i,j) 到底层的最大和”子问题。路径历史不再重要；当前位置已经包含未来需要的全部信息。
2. 状态设计卡
这里采用自底向上的语义：
| 问题 | 本例答案 |
|---|---|
| 阶段/规模 | 正在处理的行 i |
| 状态语义 | f[i][j]：从 (i,j) 出发走到底层可获得的最大路径和 |
| 第一步决策 | 下一步走 (i+1,j) 或 (i+1,j+1) |
| 转移 | f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]) |
| 边界 | 底层 f[n-1][j]=a[n-1][j] |
| 计算顺序 | 行号从 n-2 递减到 0 |
| 答案位置 | f[0][0] |
3. 手算一遍
底层直接是 [4,1,8,3]。向上一行合并：
| 位置 | 两个后继 | 新值 |
|---|---|---|
6 | 4,1 | 6+max(4,1)=10 |
5 | 1,8 | 5+max(1,8)=13 |
7 | 8,3 | 7+max(8,3)=15 |
再得到第二行 [16,19]，顶端为 2+max(16,19)=21。
PROP性质 · 计算顺序来自依赖边
不是因为“二维 DP 通常从下往上”才这样循环，而是因为 f[i][j] 依赖下一行。必须先算依赖的状态，再算当前状态。把所有依赖边画出来后，循环顺序就是这张状态 DAG 的一种拓扑序。
4. 正确性
PROOF证明
对行号自底向上归纳。底层没有后续选择，状态值显然就是自身权值。假设第 i+1 行所有状态都已给出从对应位置到底层的最优值。从 (i,j) 的第一步只有两个合法后继；选择更大的后继最优值，再加当前权值，既覆盖所有合法路径，又不会比其中任意路径差。因此第 i 行递推正确，最终 f[0][0] 正确。
5. C++17 实现与空间压缩
#include <algorithm>
#include <iostream>
#include <vector>
long long maximumPathSum(const std::vector<std::vector<int>>& triangle) {
std::vector<long long> f(triangle.back().begin(), triangle.back().end());
for (int i = static_cast<int>(triangle.size()) - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
f[j] = triangle[i][j] + std::max(f[j], f[j + 1]);
}
}
return f[0];
}
int main() {
std::vector<std::vector<int>> triangle{
{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}
};
std::cout << maximumPathSum(triangle) << '\n';
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
O(·)复杂度 · 数字三角形
三角形共有
WARN易错点 · 压缩后仍要尊重读写关系
循环到 j 时会读取旧的 f[j] 和 f[j+1]，然后覆盖 f[j]。本例从左到右安全，因为尚未覆盖的 f[j+1] 仍属于下一行。若改成相反的状态定义，安全方向也可能随之改变。
迁移问题： 如果要求输出具体路径，只保存最优值还不够；需要记录每个位置选择了哪个后继，或在值表上重新追踪。见记忆化到递推中的方案还原。
两个迁移视角：DP 不等于“数组题”
迁移案例 A · Floyd 本来就是按阶段扩张的 DP
在 Floyd 最短路中，可定义：
最后加入中间点 k 时，最短路要么不用 k，要么经过 k：
这里的阶段不是数组下标，而是“允许使用的中间点集合”。空间压缩后就是常见的三重循环。可回看最短路径，把图算法中的 dist 重新读成状态表。
迁移案例 B · 跳跃游戏外表相同，方法可能不同
若只问“能否到达末尾”，维护当前最远可达位置即可，贪心能把状态压成一个边界。若改问“到达每个位置的方案数”，单个最远边界丢失了路径数量，必须保留更多状态；若再加入少量特殊传送门，搜索也可能更直接。
ANTI反例 · 看到序列就套线性 DP
输入是数组只说明数据如何存储，不说明问题具有怎样的状态。nums[i] 可能是位置、边权、事件时间或物品价值。算法分类来自“哪些历史会影响未来”，不是来自变量类型。
一张统一的状态设计卡
以后遇到 DP 题，先在草稿纸上填这张卡，再写代码：
| 顺序 | 必答问题 | 自检方式 |
|---|---|---|
| 1 | 暴力搜索每一步在选什么？ | 能画出至少两层选择树 |
| 2 | 哪些递归参数完整描述剩余问题？ | 相同参数的调用能否直接复用答案 |
| 3 | f[...] 的一句话语义是什么？ | 包含范围、条件和目标，不使用含糊的“答案” |
| 4 | 最后一步/第一步决策是什么？ | 转移是否覆盖所有合法情况且不漏不重 |
| 5 | 边界和不可达值是什么？ | 空输入、最小规模、全负数等是否有定义 |
| 6 | 依赖方向是什么？ | 当前状态计算时，所有前驱是否已经求出 |
| 7 | 答案在哪里？ | 是 f[n]、max(f)，还是多个末态聚合 |
| 8 | 复杂度从何而来？ | 状态数 × 每个状态的转移数 |
| 9 | 是否需要还原方案？ | 仅有最优值能否回答题目全部输出 |
| 10 | 如何证伪自己？ | 写小暴力、极端边界和最小反例 |
状态定义是合同，转移只是这个合同的推论。 如果转移怎么也写不顺，优先检查状态语义，而不是增加更多 if。
全章路线：核心、进阶与选学
本轮已经落地的前五篇可以直接阅读：
- 本页：方法边界与全章地图；
- 动态规划思维与状态设计：用四个完整模型练习状态语义；
- 从记忆化搜索到递推：把递归参数翻译成表格与循环；
- 线性与网格动态规划：从依赖几何确定方向与压缩；
- 背包动态规划：理解物品次数、目标语义与循环顺序。
后续页面按以下层次规划，尚未创建空白占位：
| 层次 | 计划页面 | 学习目标 | 先修 |
|---|---|---|---|
| 核心必修 | 05-sequence-and-partition-dp.md | LCS、LIS、编辑距离与最后分界点 | 01～03 |
| 核心必修 | 06-state-machine-dp.md | 股票等有限历史状态 | 01、03 |
| 核心必修 | 07-interval-dp.md | 按区间长度枚举分界点 | 01～03 |
| 进阶 | 08-state-compression-dp.md | 子集、排列型、TSP；理解集合状态 | 位运算、记忆化 |
| 进阶 | 09-digit-dp.md | 上界约束、前导零与数位前缀 | 02、计数基础 |
| 进阶 | 10-tree-and-graph-dp.md | 树上选/不选、DAG 与拓扑依赖 | 树、图、DFS |
| 选学 | 11-counting-probability-and-game-dp.md | 数量、概率、期望与胜负状态值 | 组合/概率/博弈基础 |
| 选学地图 | 12-dp-optimization-and-advanced-topics.md | 从状态数和转移代价定位优化入口 | 核心模型全部完成 |
插头 DP、SOS DP、动态 DP、DP 套 DP、四边形不等式、斜率优化、WQS 二分和 Slope Trick 会出现在高阶地图中，但不会和爬楼梯并列成同等必修负担。
已落地的 Lab 路线
Chapter 14 目前收录 30 个 Exercise Program Lab，稳定编号为 14E01～14E30。这些题目按本章的学习主线分成五组：
| 范围 | 训练重点 |
|---|---|
14E01～14E05 | 从题意提取状态、转移、初值与答案位置 |
14E06～14E08 | 记忆化搜索、缓存设计与递归边界 |
14E09～14E17 | 线性 DP、网格 DP、序列 DP 与区间 DP |
14E18～14E26 | 0-1、完全、多重和二维费用背包 |
14E27～14E30 | 分组背包、混合背包、依赖背包与至少装满 |
每个 Lab 都使用标准输入输出、C++17、20 个公开测试点和统一评分工具。Theory 与 Project 暂时保持空分类，不为填满导航制造占位题。
学习建议
第一次阅读时，不要急着背下所有题型。先完成 01～04，并坚持对每道例题口述状态语义。能不看代码写出“范围 + 条件 + 目标”，才算真正掌握状态。
参考与延伸
- 灵茶山艾府：动态规划题单提供了由入门、网格、背包到区间、状压、数位、树形、图上和优化专题的训练梯度。本章借鉴其题型聚类，但题意均压缩改写，代码独立实现。
- OI Wiki：动态规划提供完整知识地图；动态规划基础用于校验最优子结构、无后效性、阶段/状态/决策与 DAG 视角；背包 DP用于校验背包模型边界。
- 分析复杂度时，可回看时间与空间复杂度，把“状态数 × 单状态转移数”落实为可核验的量。
外部资料用于确定覆盖范围和训练梯度，不在本站复制题解、代码或完整题单。真正要带走的是一套可以迁移到新问题的推导过程。