动态规划的三种状态设计范式:从暴力到最优
DP 的难点从来不在转移方程,而在于状态怎么定义。同一个问题,dp[i][j] 和 dp[i][j][k] 的写法天差地别,复杂度可能从 变成 ;定义错了,不仅慢,还可能算出一个下标越界、语义不通的数组。
好消息是,竞赛里绝大多数 DP 题的状态设计只落在三种范式里。认出范式,状态通常就呼之欲出了。本文就把这三种范式讲透。
思路
一、先看暴力为什么慢:状态数爆炸
任何 DP 都是”用空间换时间”——把已经算过的中间结果存下来,避免重复计算。但这里有个陷阱:存下来的状态数本身可能是天文数字。
举个具体例子。求 到 的最短路径,图有 个点。如果用最朴素的暴搜(DFS 枚举所有走法),走 个点最多有 条路径, 时超过 360 万, 时彻底爆炸。
于是我们想到”记录中间状态”。一个自然的想法是:记录”当前站在哪个点”。 但这样不够——同一个点,用时 3 步到达和用时 7 步到达,后续能走的最优路线完全不同。所以还得记录步数,状态变成 dp[点][步数],共 个。
这已经是巨大的改进( 远小于 ),但还能更好。关键观察是:如果我们只关心”最短距离”,那么”用更多步数到达同一个点”永远不优。于是 dp[点] 只需要存一个数——到该点的最短距离。这就把 压到了 。
这一步的本质,就是”状态只保留决策所需的最少信息”。 三种范式,本质上是三种不同的”砍状态”手法:
- 依赖方向是近邻 → 砍掉历史,只留前 个(线性递推)
- 对每个物品做二元决策 → 砍掉”用了哪些物品”这一维,改用一维容量滚动(背包)
- 状态本身需要描述”进度/集合” → 这维砍不掉,必须显式定义并压缩(状态机 / 状压)
二、范式一:线性递推与滚动数组
识别信号:转移方程里只出现 、 这种”近邻”,不出现 ()也不需要记额外维度。
最典型的例子是爬楼梯: 表示爬到第 级台阶的方式数,。这里 只依赖前两项,于是用长度为 3 的循环数组就够:
1 | long long f[3] = {1, 1, 2}; // f[0]=1, f[1]=1, f[2]=2 |
空间从 降到 。为什么能这么写?因为 f[i] 一旦算出来,f[i-3] 就再也用不到了——信息没有丢失。
编辑距离更能说明问题。 标准二维写法是 表示 的前 个字符转成 的前 个字符的最少操作数,转移用到 、、。直接开 数组, 时就是 400 万个 int,约 16MB,能过但浪费。
现在观察依赖方向:算第 行时,只需要第 行和第 行自己的左边。 所以第 行及更早的行都可以扔掉,滚动成两行(一维的 g[j]):
1 | // g[j] 复用为 dp[i][j]。进入第 i 轮前,g[j] 存的是 dp[i-1][j]。 |
这里有两个极易出错的细节,也是范式一和范式二的分水岭。
第一,dp[i-1][j-1] 必须用 prev 单独托住。 图省事写成 g[j] = g[j-1] 是错的——g[j-1] 在此刻已经是 而不是 ,左上角的信息已经丢了,结果会偏小。同样,min(g[j], g[j-1]) 里的 g[j] 也必须在赋值前先存进 up。只要某个状态在本轮会被覆盖,而它又要参与本轮的计算,就必须先备份。
第二,内层 j 从小到大(正序)。 因为 是”本轮应该被更新”的状态,正序才能读到它的新值。而下面 0/1 背包的 是”本轮不该被更新”的状态,所以必须倒序。两者不矛盾——判据只有一个:你依赖的那个兄弟状态,本轮该不该被更新。
三、范式二:选 / 不选型(背包)
识别信号:题面里出现”每个物品最多选一次””每个元素只能用一次”,且答案要在某种”容量/预算”限制下最大化或最小化。
这类问题的思维模型是统一的:对每个物品做一个二元决策——选它,还是不选它。不选时状态不变;选时状态从”容量 “跳到”容量 “,价值增加 :
朴素写法是二维 dp[i][j](前 件物品、容量为 ),。同样地,第 层只依赖第 层,可以压成一维。
为什么一维必须倒序枚举容量
这是整个背包知识体系的核心,值得单独讲透。
我们把二维的 dp[i][j] 压进一维 dp[j]。压缩的前提是:当内层循环跑到 dp[j] 时,dp[j] 此刻的值应该恰好等于 dp[i-1][j](还没考虑第 件物品),而 dp[j-w] 应该等于 dp[i-1][j-w]。 于是 dp[j] = max(dp[i-1][j], dp[i-1][j-w]+v) 完全等价。
问题在于:如果 正序遍历会怎样?
正序时,dp[j-w] 因为 ,已经在本轮被第 件物品更新过了。它现在的值是 dp[i][j-w],也就是”第 件物品已经被用过一次“的状态。再执行 dp[j] = max(dp[j], dp[j-w]+v),等于把第 件物品用了两次——这在 0/1 背包里是非法的!
倒序时,dp[j-w] 因为 尚未被本轮触及,它的值仍是 dp[i-1][j-w],即”还没用过第 件物品”。所以只可能选它一次,语义正确。
一句话记忆:二维 DP 压成一维时,”当前状态依赖的兄弟状态”如果也在本轮被更新,就一定会出错;倒序遍历把更新方向反转,从而保证读到的是上一轮的值。 而范式一(编辑距离)依赖的是已经算好的自己前面那一格(dp[i][j-1]),那是本轮应该被更新的,所以必须正序。两者不矛盾,只是”依赖方向”与”更新方向”的相对关系不同。
顺带说明另外两种背包的遍历方向,都是同一条规则的推论:
- 完全背包(物品可用无限次): 要求用”已用过该物品”的状态再叠加一次,所以必须正序。这也解释了为什么”完全背包能装满”常常可以省略判断——正序下
dp[j]会自动被自己抬高。 - 多重背包(每种物品 个):朴素做法是把 件拆成 件 01 物品,复杂度乘 ;优化用二进制分组拆成 件,或用单调队列做到 。
从一维到二维:二维费用背包
只有一种容量限制时,状态是一维的 dp[容量]。当题目同时给出两种互相独立的限制时(比如既有体积限制、又有价值上限),状态就要升成二维:dp[a][b] 表示”体积不超过 且价值不超过 “的最优解。
这时枚举顺序的规则不变,但两个维度都要倒序。一个完整的二维费用 0/1 背包实现见文末「参考代码」一节。
先说清为什么这里能直接写成二维并省略”物品数”那一维:因为我们用的是逐物品覆盖的写法——每轮循环就地更新 dp[j][k],且靠倒序保证读到的 dp[j-s][k-v] 仍是”处理第 台之前”的值。物品维度被”倒序”这一招隐式消掉了。
顺便解释一下为什么一维背包常常写成 dp[j] 而不是”恰好装满 j”。这里用的是 dp[j] = “体积不超过 “的语义(初值全 0 表示什么都不买),所以允许”装不满”。如果改成”恰好装满”的语义,初值就必须是 (不可达)并用 -1 参与取 min 的判断,否则 dp[0] = 0 会让所有状态都可达,凭空造出合法的空方案。这两种语义不能混用,是背包最常见的隐性错误之一。
四、范式三:状态机 / 维度展开型
识别信号:状态转移天然带”阶段感”或”进度感”——你能说出”当前处于第几步””已经走过的点有哪些””还剩多少个没做”。
这一类的共同特点是:这一维信息无法通过滚动消掉,因为它本身就是状态的一部分。 但它可以被”换一种方式压缩”,于是衍生出两个重要子类。
子类 A:把”集合”压成二进制 —— 状压 DP
当”已经选过哪些元素”无法用一个数字(容量、个数)概括,但元素个数很少( 左右)时,用一个二进制整数来表示集合:第 位为 1 表示第 个元素已在集合中。
于是状态从”集合”变成 dp[S], 从 0 到 。关键洞察是:集合本身是无序的,但 DP 沿”位数”推进是天然有序的。 转移时总是从”位数少”的状态跳向”位数多”的状态,所以状态编号本身隐含了拓扑序,可以按 从小到大枚举。
一个标准例子:把 个物品分到 个仓库,每个仓库恰好分到一个,求最小总代价。状态 dp[S] 表示”前 个仓库已经分完,用掉的物品集合为 “,其中 ,转移是”把集合外的第 个物品分给第 个仓库”。
为什么这类题不能用贪心?因为代价 一般不对称,分配顺序会显著影响总代价。举个例子,代价矩阵
按物品 1,2,3 依次分配给仓库 1,2,3,总代价是 ;但如果先把物品 1 分给仓库 3(代价 100),后面就怎么排都补不回来了。只要存在两种分配顺序给出不同答案,贪心就不成立,而这里恰好如此。
时 个状态、每个状态 次转移,约 ,可行。 时状态数 ,直接爆炸——这是状压 DP 的硬天花板,识别到 偏大就该考虑别的做法(如用 的”集合 DP”处理划分问题,或换分治)。
子类 B:把”剩余量”当状态
有些题与其记录”已经用掉多少”,不如记录”还剩多少”,状态会自然得多。
比如”一只青蛙在数轴上跳,每次跳 或 米,问能否恰好跳到第 米”。直接想”到达第 米的方式数”很麻烦,因为跳跃长度不固定;换成”从 往回退,还剩 米时的方案数”,递推关系就干净了。
再如”用面值 1、2、5 的硬币凑出 分,最少几枚”。若按”已凑出金额”来推,dp[i] 需要枚举最后一枚硬币,且状态含义混杂;换成**”还差 分时,最少还需几枚”**,则 f[i] = min(f[i-1], f[i-2], f[i-5]) + 1,极其干净。
判断技巧:如果正向定义状态时转移方程很别扭,试试把”已用量”换成”剩余量”,或者把”到达”换成”倒退”。 这个转换不改变复杂度,但常常能让方程从难写变成一行。
五、看着像 DP 却该用贪心的题
这是学生最常问的问题。判别标准只有一条:贪心能否”选一个局部最优,且这个局部最优不会牺牲全局”。 具体到识别,可以用下面两组对照来训练直觉。
对照一:区间选点(贪心)vs 区间合并(DP)
- “从若干个区间里选最多个互不相交的区间” → 贪心。按右端点从小到大排序,每次选右端点最小且不冲突的。理由是右端点越小,留给后面的空间越大,”选得越早越不亏”,每一步的局部最优恰好安全。
- “把若干个区间合并,要求合并后总长度最小” → DP。因为合并方式影响后续,且代价随合并过程变化,”当前合并不吃亏”推不出来。
对照二:分糖果(贪心)vs 最少糖果(需要调整)
“每个孩子满意度 ,相邻两个孩子糖果数不能相同,求最少糖果数”——如果满意度已经单调,相邻约束不会造成矛盾,确实可以贪心;但满意度乱序时会矛盾,必须用 DP 或”先按满意度排序再贪心分配、再按原序调整”。
这里给出一个最值得记住的具体例子:最优合并问题(石子合并)。
有 堆石子 ,每次必须合并相邻的两堆,代价为两堆石子数之和,求把 堆合并成一堆的最小总代价。
它的朴素贪心是”每次合并当前相邻的最小两堆”,看起来非常自然,但它是错的。用 完整推演一遍:
- 贪心:相邻最小对是 ,代价 9,得
[10,10,9,12];相邻最小对是 ,代价 19,累计 28,得[10,19,12];再合并 ,累计 57,得[29,12];最后 ,累计 98。 - 最优:先把
[10,10]和[6,3,12]分开,最终合并 堆,代价 41;左边 ;右边先合并 (代价 9),再 (代价 21)。总代价 。
同一组石子,贪心比最优多花了 7。 为什么?因为贪心只看”当前相邻两堆最小”,却不知道合并出的”新堆”会参与下一轮,从而把本来便宜的元素拖进了昂贵的最终合并里。贪心把 和 早早合并成 ,这个 随后被迫与 合并成 、再与另一个 合成 ;而最优方案让 和 在区间内部消化掉,避免了这个连锁放大。
而 DP 状态 dp[l][r](把第 到 堆合并成一堆的最小代价)枚举的是最后一次合并的分割点 :
就是第 堆的总和,可用前缀和 求出,整体 。
(顺便说明:写这个题时有个细节极易踩坑——“合并最小两堆”必须限定相邻。如果允许跨过中间的石子直接合并,那等价于”两堆合并”的另一个问题,代价会明显变小,两者不能混谈。上面所有推演都严格遵守相邻约束。)
这里有一个识别贪心失败的通用技巧:自己动手跑一遍小数据。 上例中贪心第一步选 (代价 9)确实是最便宜的一步,但一步最优不等于全局最优——这种”局部最优、全局吃亏”的情形,就是必须换 DP 的信号。 反过来,如果你为贪心能写出一句”选它不亏”的形式化证明(比如区间选点的”右端点越小,留给后面的空间越大”),那才放心用。
六、实战决策顺序
面对一道疑似 DP 的题,按这个顺序想:
- 暴力枚举的状态数是多少? 如果已经小到能过(比如 且 ),别急着写 DP,但要注意状压的上限。
- 状态里有哪些维度? 逐个问:这个维度是”位置/进度”(→ 范式一或三)、”容量”(→ 范式二)、还是”集合”(→ 范式三子类 A)?
- 哪些维度能砍? 依赖方向是近邻的、且只保留最优值的,可以滚动掉;靠倒序能隐式消掉”物品”维的,也可以砍。
- 剩下的维度能否合并或换表示? 两个数值限制 → 合并成一个状态;”已用量”别扭 → 换成”剩余量”。
- 回头验证是否真需要 DP。 如果问题是”最大/最小 + 选择不互相影响 + 局部不亏”,贪心更简单。
参考代码(C++17)
题目:有 台设备,第 台设备的体积是 ,价值是 。厂房空间上限为 ,预算上限为 。每台设备最多买 1 台,求在空间和预算都不超的前提下能获得的最大总价值。
输入第一行
n V C,接下来 行每行两个整数s_i v_i。,,。
1 |
|
正确性
证明本文代码(二维费用背包)的正确性,用 DP 的标准两段论。
定义:dp_i[j][k] 表示只考虑前 台设备、体积上限 、价值上限 时能获得的最大总价值。
转移的完备性与合法性:考虑第 台设备 。任何最优解必然落入以下两类之一——
- 不买第 台:此时方案只依赖前 台,最优值为 ;
- 买了第 台:去掉它后,剩余方案占用体积 、价值 ,最优值为 。
两类互斥且穷尽所有方案,故 。由于 ,第二类方案的资源占用确实在合法上限内,转移不会产生非法解。∎
循环顺序保证等价性: 与 均倒序,保证转移右侧的 dp[j-s][k-v](因 ,其所在行尚未被本轮触碰)读取到的正是 。因此一维数组上执行的操作与二维递推式完全等价,这是二维压一维的正确性依据。∎
初值的合理性:dp[j][k] = 0 表示”一台都不买”,这在任意非负的 下都是合法方案(体积 0、价值 0 均不超限),因此 0 就是”体积不超过 “这一语义下的正确初值,不存在凭空多算。∎
最终答案:dp[V][C] 使用的正是题目给定的两个上限。由 可知 dp[j][k] 关于 单调不减,故取满上限处即为全局最优。∎
范式一的正确性同理:滚动数组丢弃的第 行,在第 行及其之后的转移中都不再被引用,丢弃不损失任何信息。
复杂度
- 线性递推(爬楼梯):时间 ,滚动后空间 。
- 编辑距离:时间 ,二维空间 ;滚动后空间 或 (按行滚动只依赖上一行)。
- 0/1 背包(一维):时间 ,空间 。
- 二维费用背包:时间 ,空间 。本文规模 次转移,C++ 能过(内存约 MB)。若数据更大,可把体积维也压掉:先对体积做一维 0/1 背包筛选,再枚举价值维,或改用”枚举价值、滚动体积”的写法。
- 状压 DP:时间 ,空间 , 附近是甜点区。
- 石子合并:时间 ,空间 。
易错点清单
- 01 背包正序枚举容量。 最高频的 WA 原因,结果偏大(同一物品被重复使用),但不崩、不报错,只能靠小数据对拍发现。记牢:01 倒序,完全正序。
- 二维费用背包只倒序一个维度。 两个容量维度都要倒序,漏掉任何一个同样会重复选物品。
- 把”恰好装满”和”不超过”两种语义混用。 “不超过”初值全 0;”恰好”初值 且取 min/max 时要判不可达。混用会凭空生成空方案。
- 多维背包中某一维没倒序就以为是”完全背包”。 漏倒序不会得到完全背包,只会得到一个诡异的错误结果,和标准解对不上。定位方法是打印中间状态检查。
- 滚动数组的正负序搞反。 判据是”依赖的兄弟状态是否在本轮被更新过”:编辑距离依赖本轮已更新的
dp[i][j-1],正序;0/1 背包依赖本轮未更新的dp[j-w],倒序。记不住就画一遍数据流向。 - 状压 DP 超 上限。 是硬约束, 就是 3300 万状态、乘转移次数基本必挂。看到 偏大要立刻考虑分治、 集合 DP 或换模型。
- 状态定义时把”最优”和”可行”混淆。
dp[i]若定义为”是否存在方案”(布尔),转移里的or会丢信息,无法累加计数。要计数就必须存”方案数”(长整型),要最大化就必须存”最优值”,两者不能混。 - 计数 DP 忘记取模或用 int 溢出。 方案数增长极快( 级别),CSP/NOIP 里通常要求对 取模,且中间乘法要转
long long。 - 贪心用”看起来最优”代替”证明最优”。 用石子合并那个反例( 贪心 98 vs 最优 91)随时自测:能否为贪心写出一句”选它不亏”的证明?写不出来就别用。
- 该用 DP 时用贪心,该用贪心时用 DP。 权衡标准是复杂度与状态的直观性:DP 更”笨”但更可靠,贪心更巧但需要证明。 考场时间紧时,优先写”能立刻说清转移方程”的 DP,把贪心留到有把握的简单结构上。