动态规划
01 / 共享的机制
一张表格逐格填充自己 —— 每一格都由 常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。
在上面选一个子模式。每个子模式都可以单独跳转 —— 从题目最像的那个开始。
↑ 选一个— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态