动态规划的三种状态设计范式:从暴力到最优

DP 的难点从来不在转移方程,而在于状态怎么定义。同一个问题,dp[i][j] 和 dp[i][j][k] 的写法天差地别,复杂度可能从 O(n3)O(n^3) 变成 O(n)O(n);定义错了,不仅慢,还可能算出一个下标越界、语义不通的数组。

好消息是,竞赛里绝大多数 DP 题的状态设计只落在三种范式里。认出范式,状态通常就呼之欲出了。本文就把这三种范式讲透。

思路

一、先看暴力为什么慢:状态数爆炸

任何 DP 都是”用空间换时间”——把已经算过的中间结果存下来,避免重复计算。但这里有个陷阱:存下来的状态数本身可能是天文数字。

举个具体例子。求 AA 到 BB 的最短路径,图有 nn 个点。如果用最朴素的暴搜(DFS 枚举所有走法),走 nn 个点最多有 n!n! 条路径,n=10n = 10 时超过 360 万,n=20n = 20 时彻底爆炸。

于是我们想到”记录中间状态”。一个自然的想法是:记录”当前站在哪个点”。 但这样不够——同一个点,用时 3 步到达和用时 7 步到达,后续能走的最优路线完全不同。所以还得记录步数,状态变成 dp[点][步数],共 n×mn \times m 个。

这已经是巨大的改进(n×mn \times m 远小于 n!n!),但还能更好。关键观察是:如果我们只关心”最短距离”,那么”用更多步数到达同一个点”永远不优。于是 dp[点] 只需要存一个数——到该点的最短距离。这就把 O(nm)O(nm) 压到了 O(n)O(n)。

这一步的本质,就是”状态只保留决策所需的最少信息”。 三种范式,本质上是三种不同的”砍状态”手法:

  1. 依赖方向是近邻 → 砍掉历史,只留前 kk 个(线性递推)
  2. 对每个物品做二元决策 → 砍掉”用了哪些物品”这一维,改用一维容量滚动(背包)
  3. 状态本身需要描述”进度/集合” → 这维砍不掉,必须显式定义并压缩(状态机 / 状压)

三种状态设计范式:箭头就是状态依赖方向

二、范式一:线性递推与滚动数组

识别信号:转移方程里只出现 f[i−1]f[i-1]、f[i−2]f[i-2] 这种”近邻”,不出现 f[j]f[j](j<i−2j < i-2)也不需要记额外维度。

最典型的例子是爬楼梯:f[i]f[i] 表示爬到第 ii 级台阶的方式数,f[i]=f[i−1]+f[i−2]f[i] = f[i-1] + f[i-2]。这里 f[i]f[i] 只依赖前两项,于是用长度为 3 的循环数组就够:

1
2
3
4
long long f[3] = {1, 1, 2};      // f[0]=1, f[1]=1, f[2]=2
for (int i = 3; i <= n; ++i) {
f[i % 3] = f[(i-1) % 3] + f[(i-2) % 3];
}

空间从 O(n)O(n) 降到 O(1)O(1)。为什么能这么写?因为 f[i] 一旦算出来,f[i-3] 就再也用不到了——信息没有丢失。

编辑距离更能说明问题。 标准二维写法是 dp[i][j]dp[i][j] 表示 ss 的前 ii 个字符转成 tt 的前 jj 个字符的最少操作数,转移用到 dp[i−1][j−1]dp[i-1][j-1]、dp[i−1][j]dp[i-1][j]、dp[i][j−1]dp[i][j-1]。直接开 O(nm)O(nm) 数组,n,m=2000n,m = 2000 时就是 400 万个 int,约 16MB,能过但浪费。

现在观察依赖方向:算第 ii 行时,只需要第 i−1i-1 行和第 ii 行自己的左边。 所以第 i−2i-2 行及更早的行都可以扔掉,滚动成两行(一维的 g[j]):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// g[j] 复用为 dp[i][j]。进入第 i 轮前,g[j] 存的是 dp[i-1][j]。
int m = (int)t.size();
vector<int> g(m + 1);
for (int j = 0; j <= m; ++j) g[j] = j; // dp[0][j] = j(全靠插入)

for (int i = 1; i <= (int)s.size(); ++i) {
int prev = g[0]; // 托住 dp[i-1][0],它是下一列要用的左上角
g[0] = i; // dp[i][0] = i(全靠删除)
for (int j = 1; j <= m; ++j) {
int up = g[j]; // 先抢救 dp[i-1][j],覆盖后就永远没有了
if (s[i-1] == t[j-1]) {
g[j] = prev; // 字符相同 -> dp[i-1][j-1]
} else {
g[j] = min(up, g[j-1]) + 1; // up=dp[i-1][j],g[j-1]=dp[i][j-1]
}
prev = up; // 为下一列托住 dp[i-1][j]
}
}

这里有两个极易出错的细节,也是范式一和范式二的分水岭。

第一,dp[i-1][j-1] 必须用 prev 单独托住。 图省事写成 g[j] = g[j-1] 是错的——g[j-1] 在此刻已经是 dp[i][j−1]dp[i][j-1] 而不是 dp[i−1][j−1]dp[i-1][j-1],左上角的信息已经丢了,结果会偏小。同样,min(g[j], g[j-1]) 里的 g[j] 也必须在赋值前先存进 up。只要某个状态在本轮会被覆盖,而它又要参与本轮的计算,就必须先备份。

第二,内层 j 从小到大(正序)。 因为 dp[i][j−1]dp[i][j-1] 是”本轮应该被更新”的状态,正序才能读到它的新值。而下面 0/1 背包的 dp[j−wi]dp[j-w_i] 是”本轮不该被更新”的状态,所以必须倒序。两者不矛盾——判据只有一个:你依赖的那个兄弟状态,本轮该不该被更新。

三、范式二:选 / 不选型(背包)

识别信号:题面里出现”每个物品最多选一次””每个元素只能用一次”,且答案要在某种”容量/预算”限制下最大化或最小化。

这类问题的思维模型是统一的:对每个物品做一个二元决策——选它,还是不选它。不选时状态不变;选时状态从”容量 jj“跳到”容量 j−wij - w_i“,价值增加 viv_i:

dp[j]=max⁡(dp[j], dp[j−wi]+vi)dp[j] = \max\big(dp[j],\ dp[j - w_i] + v_i\big)

朴素写法是二维 dp[i][j](前 ii 件物品、容量为 jj),O(nV)O(nV)。同样地,第 ii 层只依赖第 i−1i-1 层,可以压成一维。

为什么一维必须倒序枚举容量

这是整个背包知识体系的核心,值得单独讲透。

我们把二维的 dp[i][j] 压进一维 dp[j]。压缩的前提是:当内层循环跑到 dp[j] 时,dp[j] 此刻的值应该恰好等于 dp[i-1][j](还没考虑第 ii 件物品),而 dp[j-w] 应该等于 dp[i-1][j-w]。 于是 dp[j] = max(dp[i-1][j], dp[i-1][j-w]+v) 完全等价。

问题在于:如果 jj 正序遍历会怎样?

正序时,dp[j-w] 因为 j−w<jj - w < j,已经在本轮被第 ii 件物品更新过了。它现在的值是 dp[i][j-w],也就是”第 ii 件物品已经被用过一次“的状态。再执行 dp[j] = max(dp[j], dp[j-w]+v),等于把第 ii 件物品用了两次——这在 0/1 背包里是非法的!

倒序时,dp[j-w] 因为 j−w<jj-w < j 尚未被本轮触及,它的值仍是 dp[i-1][j-w],即”还没用过第 ii 件物品”。所以只可能选它一次,语义正确。

一句话记忆:二维 DP 压成一维时,”当前状态依赖的兄弟状态”如果也在本轮被更新,就一定会出错;倒序遍历把更新方向反转,从而保证读到的是上一轮的值。 而范式一(编辑距离)依赖的是已经算好的自己前面那一格(dp[i][j-1]),那是本轮应该被更新的,所以必须正序。两者不矛盾,只是”依赖方向”与”更新方向”的相对关系不同。

顺带说明另外两种背包的遍历方向,都是同一条规则的推论:

  • 完全背包(物品可用无限次):dp[j]=max⁡(dp[j],dp[j−w]+v)dp[j] = \max(dp[j], dp[j-w]+v) 要求用”已用过该物品”的状态再叠加一次,所以必须正序。这也解释了为什么”完全背包能装满”常常可以省略判断——正序下 dp[j] 会自动被自己抬高。
  • 多重背包(每种物品 cc 个):朴素做法是把 cc 件拆成 cc 件 01 物品,复杂度乘 cc;优化用二进制分组拆成 O(log⁡c)O(\log c) 件,或用单调队列做到 O(V)O(V)。

从一维到二维:二维费用背包

只有一种容量限制时,状态是一维的 dp[容量]。当题目同时给出两种互相独立的限制时(比如既有体积限制、又有价值上限),状态就要升成二维:dp[a][b] 表示”体积不超过 aa 且价值不超过 bb“的最优解。

这时枚举顺序的规则不变,但两个维度都要倒序。一个完整的二维费用 0/1 背包实现见文末「参考代码」一节。

先说清为什么这里能直接写成二维并省略”物品数”那一维:因为我们用的是逐物品覆盖的写法——每轮循环就地更新 dp[j][k],且靠倒序保证读到的 dp[j-s][k-v] 仍是”处理第 ii 台之前”的值。物品维度被”倒序”这一招隐式消掉了。

顺便解释一下为什么一维背包常常写成 dp[j] 而不是”恰好装满 j”。这里用的是 dp[j] = “体积不超过 jj“的语义(初值全 0 表示什么都不买),所以允许”装不满”。如果改成”恰好装满”的语义,初值就必须是 −1-1(不可达)并用 -1 参与取 min 的判断,否则 dp[0] = 0 会让所有状态都可达,凭空造出合法的空方案。这两种语义不能混用,是背包最常见的隐性错误之一。

四、范式三:状态机 / 维度展开型

识别信号:状态转移天然带”阶段感”或”进度感”——你能说出”当前处于第几步””已经走过的点有哪些””还剩多少个没做”。

这一类的共同特点是:这一维信息无法通过滚动消掉,因为它本身就是状态的一部分。 但它可以被”换一种方式压缩”,于是衍生出两个重要子类。

子类 A:把”集合”压成二进制 —— 状压 DP

当”已经选过哪些元素”无法用一个数字(容量、个数)概括,但元素个数很少(n≤20n \le 20 左右)时,用一个二进制整数来表示集合:第 ii 位为 1 表示第 ii 个元素已在集合中。

于是状态从”集合”变成 dp[S],SS 从 0 到 2n−12^n - 1。关键洞察是:集合本身是无序的,但 DP 沿”位数”推进是天然有序的。 转移时总是从”位数少”的状态跳向”位数多”的状态,所以状态编号本身隐含了拓扑序,可以按 SS 从小到大枚举。

一个标准例子:把 nn 个物品分到 nn 个仓库,每个仓库恰好分到一个,求最小总代价。状态 dp[S] 表示”前 kk 个仓库已经分完,用掉的物品集合为 SS“,其中 k=popcount(S)k = \text{popcount}(S),转移是”把集合外的第 jj 个物品分给第 k+1k+1 个仓库”。

为什么这类题不能用贪心?因为代价 c[i][j]c[i][j] 一般不对称,分配顺序会显著影响总代价。举个例子,代价矩阵

c=(0110010110010)c = \begin{pmatrix} 0 & 1 & 100 \ 1 & 0 & 1 \ 100 & 1 & 0 \end{pmatrix}

按物品 1,2,3 依次分配给仓库 1,2,3,总代价是 0+0+0=00 + 0 + 0 = 0;但如果先把物品 1 分给仓库 3(代价 100),后面就怎么排都补不回来了。只要存在两种分配顺序给出不同答案,贪心就不成立,而这里恰好如此。

n≤20n \le 20 时 220=1062^{20} = 10^6 个状态、每个状态 O(n)O(n) 次转移,约 2×1072 \times 10^7,可行。n=30n = 30 时状态数 10910^9,直接爆炸——这是状压 DP 的硬天花板,识别到 nn 偏大就该考虑别的做法(如用 O(3n)O(3^n) 的”集合 DP”处理划分问题,或换分治)。

子类 B:把”剩余量”当状态

有些题与其记录”已经用掉多少”,不如记录”还剩多少”,状态会自然得多。

比如”一只青蛙在数轴上跳,每次跳 aa 或 bb 米,问能否恰好跳到第 mm 米”。直接想”到达第 ii 米的方式数”很麻烦,因为跳跃长度不固定;换成”从 mm 往回退,还剩 ii 米时的方案数”,递推关系就干净了。

再如”用面值 1、2、5 的硬币凑出 nn 分,最少几枚”。若按”已凑出金额”来推,dp[i] 需要枚举最后一枚硬币,且状态含义混杂;换成**”还差 ii 分时,最少还需几枚”**,则 f[i] = min(f[i-1], f[i-2], f[i-5]) + 1,极其干净。

判断技巧:如果正向定义状态时转移方程很别扭,试试把”已用量”换成”剩余量”,或者把”到达”换成”倒退”。 这个转换不改变复杂度,但常常能让方程从难写变成一行。

五、看着像 DP 却该用贪心的题

这是学生最常问的问题。判别标准只有一条:贪心能否”选一个局部最优,且这个局部最优不会牺牲全局”。 具体到识别,可以用下面两组对照来训练直觉。

对照一:区间选点(贪心)vs 区间合并(DP)

  • “从若干个区间里选最多个互不相交的区间” → 贪心。按右端点从小到大排序,每次选右端点最小且不冲突的。理由是右端点越小,留给后面的空间越大,”选得越早越不亏”,每一步的局部最优恰好安全。
  • “把若干个区间合并,要求合并后总长度最小” → DP。因为合并方式影响后续,且代价随合并过程变化,”当前合并不吃亏”推不出来。

对照二:分糖果(贪心)vs 最少糖果(需要调整)

“每个孩子满意度 sis_i,相邻两个孩子糖果数不能相同,求最少糖果数”——如果满意度已经单调,相邻约束不会造成矛盾,确实可以贪心;但满意度乱序时会矛盾,必须用 DP 或”先按满意度排序再贪心分配、再按原序调整”。

这里给出一个最值得记住的具体例子:最优合并问题(石子合并)。

有 nn 堆石子 a1…ana_1 \dots a_n,每次必须合并相邻的两堆,代价为两堆石子数之和,求把 nn 堆合并成一堆的最小总代价。

它的朴素贪心是”每次合并当前相邻的最小两堆”,看起来非常自然,但它是错的。用 a=[10,10,6,3,12]a = [10, 10, 6, 3, 12] 完整推演一遍:

  • 贪心:相邻最小对是 6+3=96+3=9,代价 9,得 [10,10,9,12];相邻最小对是 10+9=1910+9=19,代价 19,累计 28,得 [10,19,12];再合并 10+19=2910+19=29,累计 57,得 [29,12];最后 29+12=4129+12=41,累计 98。
  • 最优:先把 [10,10] 和 [6,3,12] 分开,最终合并 (20+21)=41(20 + 21) = 41 堆,代价 41;左边 10+10=2010+10=20;右边先合并 6+3=96+3=9(代价 9),再 9+12=219+12=21(代价 21)。总代价 41+20+9+21=9141 + 20 + 9 + 21 = \mathbf{91}。

同一组石子,贪心比最优多花了 7。 为什么?因为贪心只看”当前相邻两堆最小”,却不知道合并出的”新堆”会参与下一轮,从而把本来便宜的元素拖进了昂贵的最终合并里。贪心把 66 和 33 早早合并成 99,这个 99 随后被迫与 1010 合并成 1919、再与另一个 1010 合成 2929;而最优方案让 33 和 66 在区间内部消化掉,避免了这个连锁放大。

而 DP 状态 dp[l][r](把第 ll 到 rr 堆合并成一堆的最小代价)枚举的是最后一次合并的分割点 kk:

dp[l][r]=min⁡l≤k<r(dp[l][k]+dp[k+1][r]+∑i=lrai)dp[l][r] = \min_{l \le k < r}\Big(dp[l][k] + dp[k+1][r] + \sum_{i=l}^{r} a_i\Big)

∑i=lrai\sum_{i=l}^{r} a_i 就是第 l…rl \dots r 堆的总和,可用前缀和 O(1)O(1) 求出,整体 O(n3)O(n^3)。

(顺便说明:写这个题时有个细节极易踩坑——“合并最小两堆”必须限定相邻。如果允许跨过中间的石子直接合并,那等价于”两堆合并”的另一个问题,代价会明显变小,两者不能混谈。上面所有推演都严格遵守相邻约束。)

这里有一个识别贪心失败的通用技巧:自己动手跑一遍小数据。 上例中贪心第一步选 6+36+3(代价 9)确实是最便宜的一步,但一步最优不等于全局最优——这种”局部最优、全局吃亏”的情形,就是必须换 DP 的信号。 反过来,如果你为贪心能写出一句”选它不亏”的形式化证明(比如区间选点的”右端点越小,留给后面的空间越大”),那才放心用。

六、实战决策顺序

面对一道疑似 DP 的题,按这个顺序想:

  1. 暴力枚举的状态数是多少? 如果已经小到能过(比如 O(2n)O(2^n) 且 n≤20n \le 20),别急着写 DP,但要注意状压的上限。
  2. 状态里有哪些维度? 逐个问:这个维度是”位置/进度”(→ 范式一或三)、”容量”(→ 范式二)、还是”集合”(→ 范式三子类 A)?
  3. 哪些维度能砍? 依赖方向是近邻的、且只保留最优值的,可以滚动掉;靠倒序能隐式消掉”物品”维的,也可以砍。
  4. 剩下的维度能否合并或换表示? 两个数值限制 → 合并成一个状态;”已用量”别扭 → 换成”剩余量”。
  5. 回头验证是否真需要 DP。 如果问题是”最大/最小 + 选择不互相影响 + 局部不亏”,贪心更简单。

参考代码(C++17)

题目:有 nn 台设备,第 ii 台设备的体积是 sis_i,价值是 viv_i。厂房空间上限为 VV,预算上限为 CC。每台设备最多买 1 台,求在空间和预算都不超的前提下能获得的最大总价值。

输入第一行 n V C,接下来 nn 行每行两个整数 s_i v_i。n≤100n \le 100,V,C≤1000V, C \le 1000,si,vi≤1000s_i, v_i \le 1000。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, V, C;
cin >> n >> V >> C;

// dp[j][k]:已考虑的设备中,体积不超过 j 且价值不超过 k 时的最大总价值
// 全 0 初始化表示"什么都不买",是"体积/价值不超过上限"这一语义下的合法初值
vector<vector<int>> dp(V + 1, vector<int>(C + 1, 0));

for (int i = 0; i < n; ++i) {
int s, v;
cin >> s >> v;

// 这台设备单独就超出任一上限时,永远不可能被选中,直接跳过
if (s > V || v > C) continue;

// 两个容量维度都必须倒序,保证第 i 台设备最多被选一次。
// 若任一维度正序,dp[j-s][k-v] 就已被本轮更新成"用过这台设备"的状态,
// 再叠加一次相当于把同一台设备买了两份,答案会偏大。
for (int j = V; j >= s; --j) { // 体积维倒序
for (int k = C; k >= v; --k) { // 价值维倒序
int skip = dp[j][k]; // 不买这台
int take = dp[j - s][k - v] + v; // 买这台:占 s 体积、v 价值
dp[j][k] = max(skip, take);
}
}
}

// dp 关于 j、k 单调不减,故取满两个上限处即为最优答案
cout << dp[V][C] << '\n';
return 0;
}

正确性

证明本文代码(二维费用背包)的正确性,用 DP 的标准两段论。

定义:dp_i[j][k] 表示只考虑前 ii 台设备、体积上限 jj、价值上限 kk 时能获得的最大总价值。

转移的完备性与合法性:考虑第 ii 台设备 (s,v)(s, v)。任何最优解必然落入以下两类之一——

  • 不买第 ii 台:此时方案只依赖前 i−1i-1 台,最优值为 dpi−1[j][k]dp_{i-1}[j][k];
  • 买了第 ii 台:去掉它后,剩余方案占用体积 ≤j−s\le j - s、价值 ≤k−v\le k - v,最优值为 dpi−1[j−s][k−v]+vdp_{i-1}[j-s][k-v] + v。

两类互斥且穷尽所有方案,故 dpi[j][k]=max⁡(dpi−1[j][k], dpi−1[j−s][k−v]+v)dp_i[j][k] = \max\big(dp_{i-1}[j][k],\ dp_{i-1}[j-s][k-v] + v\big)。由于 s,v≥0s, v \ge 0,第二类方案的资源占用确实在合法上限内,转移不会产生非法解。∎

循环顺序保证等价性:jj 与 kk 均倒序,保证转移右侧的 dp[j-s][k-v](因 j−s<jj-s < j,其所在行尚未被本轮触碰)读取到的正是 dpi−1[j−s][k−v]dp_{i-1}[j-s][k-v]。因此一维数组上执行的操作与二维递推式完全等价,这是二维压一维的正确性依据。∎

初值的合理性:dp[j][k] = 0 表示”一台都不买”,这在任意非负的 j,kj, k 下都是合法方案(体积 0、价值 0 均不超限),因此 0 就是”体积不超过 jj“这一语义下的正确初值,不存在凭空多算。∎

最终答案:dp[V][C] 使用的正是题目给定的两个上限。由 ≥0\ge 0 可知 dp[j][k] 关于 j,kj, k 单调不减,故取满上限处即为全局最优。∎

范式一的正确性同理:滚动数组丢弃的第 i−ki-k 行,在第 ii 行及其之后的转移中都不再被引用,丢弃不损失任何信息。

复杂度

  • 线性递推(爬楼梯):时间 O(n)O(n),滚动后空间 O(1)O(1)。
  • 编辑距离:时间 O(nm)O(nm),二维空间 O(nm)O(nm);滚动后空间 O(m)O(m) 或 O(min⁡(n,m))O(\min(n,m))(按行滚动只依赖上一行)。
  • 0/1 背包(一维):时间 O(nV)O(nV),空间 O(V)O(V)。
  • 二维费用背包:时间 O(nVC)O(nVC),空间 O(VC)O(VC)。本文规模 100×1000×1000=108100 \times 1000 \times 1000 = 10^8 次转移,C++ 能过(内存约 1001×1001×4≈41001 \times 1001 \times 4 \approx 4MB)。若数据更大,可把体积维也压掉:先对体积做一维 0/1 背包筛选,再枚举价值维,或改用”枚举价值、滚动体积”的写法。
  • 状压 DP:时间 O(2n⋅n)O(2^n \cdot n),空间 O(2n)O(2^n),n≤20n \le 20 附近是甜点区。
  • 石子合并:时间 O(n3)O(n^3),空间 O(n2)O(n^2)。

易错点清单

  1. 01 背包正序枚举容量。 最高频的 WA 原因,结果偏大(同一物品被重复使用),但不崩、不报错,只能靠小数据对拍发现。记牢:01 倒序,完全正序。
  2. 二维费用背包只倒序一个维度。 两个容量维度都要倒序,漏掉任何一个同样会重复选物品。
  3. 把”恰好装满”和”不超过”两种语义混用。 “不超过”初值全 0;”恰好”初值 −1-1 且取 min/max 时要判不可达。混用会凭空生成空方案。
  4. 多维背包中某一维没倒序就以为是”完全背包”。 漏倒序不会得到完全背包,只会得到一个诡异的错误结果,和标准解对不上。定位方法是打印中间状态检查。
  5. 滚动数组的正负序搞反。 判据是”依赖的兄弟状态是否在本轮被更新过”:编辑距离依赖本轮已更新的 dp[i][j-1],正序;0/1 背包依赖本轮未更新的 dp[j-w],倒序。记不住就画一遍数据流向。
  6. 状压 DP 超 nn 上限。 2n2^n 是硬约束,n=25n = 25 就是 3300 万状态、乘转移次数基本必挂。看到 nn 偏大要立刻考虑分治、O(3n)O(3^n) 集合 DP 或换模型。
  7. 状态定义时把”最优”和”可行”混淆。 dp[i] 若定义为”是否存在方案”(布尔),转移里的 or 会丢信息,无法累加计数。要计数就必须存”方案数”(长整型),要最大化就必须存”最优值”,两者不能混。
  8. 计数 DP 忘记取模或用 int 溢出。 方案数增长极快(21002^{100} 级别),CSP/NOIP 里通常要求对 109+710^9 + 7 取模,且中间乘法要转 long long。
  9. 贪心用”看起来最优”代替”证明最优”。 用石子合并那个反例([10,10,6,3,12][10,10,6,3,12] 贪心 98 vs 最优 91)随时自测:能否为贪心写出一句”选它不亏”的证明?写不出来就别用。
  10. 该用 DP 时用贪心,该用贪心时用 DP。 权衡标准是复杂度与状态的直观性:DP 更”笨”但更可靠,贪心更巧但需要证明。 考场时间紧时,优先写”能立刻说清转移方程”的 DP,把贪心留到有把握的简单结构上。