动态规划
01 / 共享的机制
一张表格逐格填充自己 —— 每一格都由 常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。
02 / 一句话本质
状态是一个区间(i, j);答案由[i, j]内部更小的区间组合而成。按区间长度递增的顺序填表,而不是按行 — 只有这个方向能保证依赖项已经就绪。
题目最长回文子串输入"babad"n5
b0
a1
b2
a3
d4
0
1
2
3
4
0
·
·
·
·
·
1
·
·
·
·
2
·
·
·
3
·
·
4
·
每个 dp[i][j] 回答:“s[i..j] 是回文吗?”按区间长度填表 —— 先长度 1,再 2,再 3,……
步
0 / 12
区间长度
—
最优长度
1
最优区间
[0, 0]
0 / 12
03 / 模式骨架
# 区间 DP —— 按长度填表,而不是按行# 基线:长度 1(以及通常的长度 2)for len in 2..n:for i in 0..n−len:j ← i + len − 1dp[i][j] ← f(dp[i+1][j−1], ...) 或在 (i, j) 中枚举分割点 kreturn dp[0][n−1]# 回文:dp[i][j] = (s[i]==s[j]) AND dp[i+1][j−1]# 矩阵链:在 (i, j) 中对 k 取最小值 dp[i][k] + dp[k+1][j] + cost
04 / 什么时候用这个模式
"区间查询"
题目问的是任意连续子数组或子串的某个性质 —— 回文、有序、平衡。子区间是头等公民。
"由内向外组合"
[i, j] 的答案只依赖严格更内部的区间 —— [i+1, j-1], 或某种 [i, k] + [k+1, j]。递归是从外层逐层剥开。"枚举分割点"
矩阵链乘、戳气球、最优 BST —— 在
(i, j) 中枚举每一个 k 后合并。这一额外的内层循环把复杂度从 O(N²) 推到 O(N³)。"上三角表"
只有
i ≤ j 的格子才有意义 —— 一半的表是空的。 填表顺序沿对角线推进:主对角线(长度 1),次对角线(长度 2),再向外扩。05 / 常见坑
i.
按行填表,而不是按长度填表。
如果你把
i 放外层、j 放内层,你会在 dp[i+1][j-1] 被填好之前就去读它 —— 那个格子属于第 i+1 行,而那一行还没轮到。 正确做法是把长度放在外层:长度为 L 的所有区间都填完之后, 才会触碰长度为 L+1 的区间。ii.
忘记把长度 2 作为独立基线。
对回文问题,
dp[i][i+1] = (s[i] == s[i+1]) 无法由通项递推得到, 因为 dp[i+1][i] 在对角线下方 —— 那是一个非法区间,而不是 false。 干净的实现一般会把长度 2 和长度 1 一并作为基线处理。iii.
对“分割点”型区间 DP 选错了分割粒度。
对矩阵链或戳气球,分割点
k 必须在 (i, j) 的内部下标上取值 —— 而 k 的含义(左半部分是 [i, k] 还是 [i, k-1])是题目相关的。此处的差一会让所有结果都崩坏。06 / 去 LeetCode 上练习
区间 DP 家族的四道题。前两道是直接读内部区间的递推(长度 2 跳跃)。 后两道需要枚举分割点 —— (i, j) 中的每个 k 都是候选。
— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态