动态规划
01 / 共享的机制
一张表格逐格填充自己 —— 每一格都由 常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。
01 / 一句话本质
一维表中的每一个单元格,都在回答同一问题的更小版本 — 按顺序填充一次,任意位置的答案都由常数个更早的单元格组合而成。
题目从不相邻的房子中偷到的最大金额输入[2, 7, 9, 3, 1, 8]
input
20
71
92
33
14
85
dp
?0
?1
?2
?3
?4
?5
每个 dp[i] 表示考虑房子 0..i 时能偷到的最大金额。从左到右填表。
步
0 / 7
i
—
选择
—
目前最大
0
0 / 7
02 / 模式骨架
# 一维 DP —— 每步在两个选项中取其一dp[0] ← 基础情形 0dp[1] ← 基础情形 1for i in 2..n−1:dp[i] ← f(dp[i−1], dp[i−2], input[i])return dp[n−1]# 打家劫舍: f = max(dp[i−1], dp[i−2] + nums[i])# 最大子数组 (Kadane): f = max(nums[i], dp[i−1] + nums[i])# 爬楼梯: f = dp[i−1] + dp[i−2]
03 / 什么时候用这个模式
"最大 / 最小 / 计数"
你在做优化或计数,且位置
i 的答案可由更小位置的答案组合得到。 如果暴力解是指数级的,就要怀疑是 DP。"不相邻 / 序列"
一种位置约束 —— 不能选相邻、必须保持顺序、必须是子序列。 每一步的选择都会与之前的选择相互影响。
"重叠子问题"
朴素递归会反复求解同一个更小的子问题。DP 把它们缓存下来。
"最优子结构"
位置
i 的最优答案,要由更小位置的最优答案组合而成,而不是任意答案。 没有这个性质,贪心不适用,DP 同样无能为力。04 / 常见坑
i.
基础情形写错。
dp[0] 和 dp[1] 是边界差一最容易出现的地方。把它们读出声: "只有一个元素时的答案" / "有两个元素时的答案"。 在写循环之前,先用最小的非平凡输入做心算验证。ii.
遍历方向不对。
递推决定了填表顺序 ——
dp[i+1] 还没写入,就不能读取。 从左到右是默认顺序,但某些问题(例如对偶形式的切钢条)需要从右到左。iii.
该用 DP 时却伸手去拿贪心。
如果每一步局部最优的选择会把你挡在全局更优解之外 (例如"现在劫掉这间小房子"让你失去"两步之后劫那间大房子"的机会),贪心就会失败。 DP 同时考察两条分支,取其最大值。
05 / 去 LeetCode 上练习
四道题,按递推所在维度排序。前三道是一维线性 DP; 第四道把你抬升到 O(N²) DP —— 表仍然是一维,只是依赖范围更宽。
— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态