动态规划
01 / 共享的机制
一张表格逐格填充自己 —— 每一格都由 常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。
02 / 一句话本质
每个物品都引发一次选或不选的决策,状态是你迄今累积的全部 —— 通常是和或容量。 二维表的一个轴是物品,另一个轴是累积状态。
题目将数组分成两个等和子集输入[1, 5, 11, 5]目标11
物品
10
51
112
53
和 →01234567891011
∅
·
·
·
·
·
·
·
·
·
·
·
·
+1
·
·
·
·
·
·
·
·
·
·
·
·
+5
·
·
·
·
·
·
·
·
·
·
·
·
+11
·
·
·
·
·
·
·
·
·
·
·
·
+5
·
·
·
·
·
·
·
·
·
·
·
·
总和 = 22,目标 = 11。每个 dp[i][s] 回答:"用前 i 个物品能否凑出和 s?"
步
0 / 50
目标
11
选择
—
答案
—
0 / 50
03 / 模式骨架
# 背包 —— 对每个物品选或不选dp[0][0] ← 基础情形(通常为 true / 0)for i in 1..n:for s in 0..target:skip ← dp[i−1][s]take ← if s ≥ w[i]: dp[i−1][s−w[i]] else falsedp[i][s] ← combine(skip, take)return dp[n][target]# 子集和: combine = OR;0/1 背包: combine = max# 完全背包(零钱兑换): 读 dp[i][s−w] 而非 dp[i−1][s−w]
04 / 什么时候用这个模式
"挑一个子集"
题目问某个子集能否满足约束,或在预算下哪个子集最优。如果物品顺序无关,就要怀疑是背包。
"重量 / 容量 / 目标"
一个数值预算(容量、和、个数)限制选择。这个预算会成为 DP 表的第二根轴。
"每个物品唯一"
标准 0/1 背包:每个物品至多取一次。如果物品可重用,就进入了完全背包领域(零钱兑换) —— 递推从当前行而非上一行读取。
"状态有两根轴"
(已处理物品数,目前和)或(已处理物品数,已用容量)。当自然状态超过两根轴时, 家族会延展 —— 但选/不选的骨架依然成立。
05 / 常见坑
i.
混淆 0/1 与完全背包。
0/1 背包读取
dp[i-1][s-w](上一行) —— 每个物品至多用一次。 完全背包读取 dp[i][s-w](当前行) —— 物品可以重复。 压缩为一维数组时,0/1 从右向左扫描;完全背包从左向右扫描。写反方向,表会悄无声息地给出错误答案。ii.
忘了对奇数总和短路。
分割等和子集要求总和为偶数 —— 奇数立刻不可能。 在 DP 运行之前抓住这一点,可以为一半的输入省下
O(N · S) 的工作。iii.
对伪多项式复杂度毫无防备。
运行时间是
O(N · S),其中 S 是一个数值目标, 不是目标的 log。N 很小但和非常大的输入(例如[10^9])会让背包 DP 不可行。识破这一点,改用其他方法 (折半搜索、分支限界)。06 / 去 LeetCode 上练习
背包家族的四道题。前三题变化的是 combine 规则(OR、计数、最大值)。 第四题转到完全背包 —— 同样的骨架,但从当前行读取。
— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态