动态规划
01 / 共享的机制
一张表格逐格填充自己 —— 每一格都由 常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。
02 / 一句话本质
状态有两个下标,(i, j) 处的答案由严格更小坐标的常数个单元格组合而成 —— 按行填表,这样每次走到一个单元格时,它的依赖都已在表中就位。题目左上 → 右下的最小路径和网格3×3
1?
3?
1?
1?
5?
1?
4?
2?
1?
每个 dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。按行填表。
步
0 / 10
已填单元格
0
选择
—
最小路径和
—
0 / 10
03 / 模式骨架
# 二维 DP —— 两个下标,读取邻居dp[0][0] ← 基础情形# 累计填充首行与首列(一维基础)for i in 1..R−1:for j in 1..C−1:dp[i][j] ← f(dp[i−1][j], dp[i][j−1], dp[i−1][j−1])return dp[R−1][C−1]# 最小路径和: f = grid[i][j] + min(top, left)# LCS: f = (s1[i]==s2[j]) ? diag+1 : max(top, left)# 编辑距离: f = (s1[i]==s2[j]) ? diag : 1 + min(top, left, diag)
04 / 什么时候用这个模式
"网格"
状态本身就是网格坐标 —— 只能向右或向下走是最典型的形态。 依赖方向永远向后,绝不会横向或向上。
"两条序列"
问题涉及两个字符串或两个数组,询问对齐、公共结构或变换 —— LCS、编辑距离、正则匹配。状态
(i, j) = "s1 的前 i 个、s2 的前 j 个"。"至多读三个邻居"
上方、左方、左上对角。如果你需要读取一个远处的单元格,说明 DP 的形式化错了—— 你大概需要不同的状态或不同的填表顺序。
"答案在角落"
最优解出现在
dp[R−1][C−1](或递推终止之处)。 如果题目要求表中途的答案,通常需要在整张表上取最大值。05 / 常见坑
i.
填表顺序违反依赖方向。
递推决定哪些单元格必须先写、哪些后写。若
dp[i][j]读取上方与左方,标准的逐行从左到右扫描就够用。 但对回文子串类 DP,需要按区间长度顺序填表。永远先问自己:我的依赖在表中相对于当前位置在哪里?ii.
输入下标与表下标差 1。
当表的大小为
(M+1) × (N+1)(双序列 DP 常见), 输入下标与表下标会差一。大部分调试时间都耗在错位的边界差一上。iii.
忘了滚动数组优化是有代价的。
压缩到单行可以把空间从
O(R·C) 降到 O(C), 但你会失去路径 —— 只剩最终代价。如果题目还要求实际路径 (例如最小路径和的具体路径,或 LCS 字符串本身),就要保留整张表。06 / 去 LeetCode 上练习
四道题,按二维表的搭建方式排序。前两道是真正的网格; 后两道是双序列 DP,网格是概念上的 —— 行是一个字符串中的位置,列是另一个字符串中的位置。
— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态