动态规划
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 / 常见坑
填表顺序违反依赖方向。
递推决定哪些单元格必须先写、哪些后写。若
dp[i][j]读取上方与左方,标准的逐行从左到右扫描就够用。 但对回文子串类 DP,需要按区间长度顺序填表。永远先问自己:我的依赖在表中相对于当前位置在哪里?输入下标与表下标差 1。
当表的大小为
(M+1) × (N+1)(双序列 DP 常见), 输入下标与表下标会差一。大部分调试时间都耗在错位的边界差一上。忘了滚动数组优化是有代价的。
压缩到单行可以把空间从
O(R·C) 降到 O(C), 但你会失去路径 —— 只剩最终代价。如果题目还要求实际路径 (例如最小路径和的具体路径,或 LCS 字符串本身),就要保留整张表。06 / 去 LeetCode 上练习
中等19
01Longest Palindromic Substring— LC 5→02Unique Paths— LC 62→03Unique Paths II— LC 63→04Minimum Path Sum— LC 64→05Edit Distance— LC 72→06Interleaving String— LC 97→07Triangle— LC 120→08Maximal Square— LC 221→09Longest Palindromic Subsequence— LC 516→10Delete Operation for Two Strings— LC 583→11Palindromic Substrings— LC 647→12Minimum ASCII Delete Sum for Two Strings— LC 712→13Minimum Falling Path Sum— LC 931→14Uncrossed Lines— LC 1035→15Longest Common Subsequence— LC 1143→16Count Square Submatrices with All Ones— LC 1277→17Count Submatrices With All Ones— LC 1504→18Maximum Number of Points with Cost— LC 1937→19Longest Ideal Subsequence— LC 2370→
困难10
01Largest Rectangle in Histogram— LC 84→02Maximal Rectangle— LC 85→03Distinct Subsequences— LC 115→04Palindrome Partitioning II— LC 132→05Dungeon Game— LC 174→06Cherry Pickup— LC 741→07Unique Paths III— LC 980→08Minimum Falling Path Sum II— LC 1289→09Cherry Pickup II— LC 1463→10Maximum Value of K Coins From Piles— LC 2218→
— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态
树形 DP
当问题定义在树上、且每个节点的答案依赖其子节点答案时使用。
打家劫舍 III · 二叉树直径 · 最大路径和
位掩码
当状态是子集(通常
N ≤ 20),且只关心选了哪些、不关心顺序时使用。分配 · TSP · 最小覆盖团队