Algorithm · Dynamic Programming
重叠子问题的记忆化艺术：五步解题法 · 线性/子序列/背包三大族 · 记忆化与递推的一体两面
重叠子问题 · 最优子结构 · 无后效性——满足才谈 DP
状态定义 → 转移方程 → 初始化 → 遍历顺序 → 返回值
线性（打家劫舍）· 子序列（LIS/LCS）· 背包（01/完全）——面试 80% 的 DP 题
Why Dynamic Programming
| 做法 | 算 fib(40) 要做多少次 | 体感 |
|---|---|---|
| 照着公式裸递归 | 约 3.3 亿次函数调用 | 笔记本上要跑好几秒 |
| 算过的记在表里 | 41 次 | 微秒级，感觉不到 |
| 从小到大顺着推 | 40 次循环 | 微秒级，且不用递归栈 |
按定义 f(n) = f(n-1) + f(n-2) 展开 f(5)：为了算 f(5) 要算 f(4) 和 f(3)；算 f(4) 又要算 f(3) 和 f(2)……你会在树上看到第二个 f(3)——一个你已经算过、却完全不记得的答案。
对斐波那契，是的。但对"求最大值"类的问题还不够：你还得保证子问题的最优解真能拼出全局最优解。举个反例——图里的"最长简单路径"，子路径最优未必拼得出全局最优，此时加表也没用。能不能加表，是前提问题，不是技巧问题。
不在填表，在"表的一行代表什么"。填表是机械劳动；难的是把"当前处境"抽象成一组参数（这就是状态定义）。同一个题状态定义错了，后面的转移方程怎么写都别扭。本 deck 的重点几乎全押在这一步。
先立三个前提（什么时候配用 DP）→ 抽出五步解题法 → 三大族（线性 / 子序列 / 背包）逐个走一遍五步 → 记忆化与递推的一体两面 → 空间优化与高频陷阱。
Prerequisites & Glossary
| 术语 | 一句话理解（先记住这个，细节后面展开） |
|---|---|
| 子问题 subproblem | 把原问题缩小规模后得到的同一个问题（f(5) 里套着的 f(4) 就是一个子问题） |
| 重叠子问题 | 展开后同一个子问题被反复求解。它是"记忆化能省钱"的前提——不重叠就不必建表 |
| 最优子结构 | 原问题的最优解能由子问题的最优解拼出来。有它，最值问题才能用 DP |
| 无后效性 | 状态一旦确定，未来怎么走只取决于当前状态值，与"怎么走到这儿"无关 |
| 状态 state | 用一组参数把"当前处境"完整描述出来，如 dp[i]、dp[i][j]。DP 最难的一步就是它 |
| 转移方程 | 状态之间的递推关系。写它的通用姿势是枚举"最后一步"的所有可能 |
| DP 表 / memo | 存放子问题答案的数组或 map。表的下标 = 状态的参数 |
| 记忆化搜索（自顶向下） | 从目标出发递归，算过的顺手记下来，下次直接查。写法最接近暴力递归 |
| 递推（自底向上） | 从最小的状态开始，按依赖顺序把整张表填满。常数更小，但需要自己定顺序 |
| 滚动数组 | 当 dp[i] 只依赖前几层时，把二维表压成一维（甚至两个变量）的省空间技巧 |
先读这几篇再回来。本 deck 默认你已经能读懂递归与数组下标：
回溯 → DP 的起点就是它那样的暴力递归
复杂度分析 → O(n²)/O(n·m) 这些账怎么算
贪心 → 另一个"每步只留一个选择"的流派
把 DP 记成一个固定动作：① 把"当前处境"用一组参数写成一个状态；② 写出"这个状态由哪些更小的状态推出来"。剩下的三件事——建表、定遍历顺序、填表——全是机械劳动。所有 DP 题的难点都不在填表，而在"用什么参数描述状态"。
它是判断"状态定义对不对"的试金石。如果发现未来的决策还要看你是怎么走到这一步的，说明状态漏了信息——正确做法是把"怎么来的"升级成状态的一个新维度（比如股票题加一维"是否持有"、带冷却的再加一维"是否处于冷却期"）。
Overlapping Subproblems
上一页说"加一张表就能从 3.3 亿次降到 40 次"——但表不是想加就能加：只有同时满足下面三个前提的问题，才配得上 DP。
递归展开后同一个子问题被反复求解——斐波那契裸递归里 f(3) 被算几万次。这是"记忆化能省钱"的前提；没有重叠（如归并排序）就不需要 DP 表。
原问题的最优解由子问题的最优解构成——"和为最大的子数组"的最优包含"以 i−1 结尾"的最优。反例：最长简单路径（图里环的存在让子路径未必最优）。
状态一经确定，未来的决策只依赖状态值、不依赖到达路径。违反时的解法：把"怎么来的"塞进状态里（升级状态维度，如带冷却的股票）。
先问"能不能定义一个无后效的状态"，再问"状态之间是否有最优子结构"，最后看"子问题是否重叠值得记忆"。顺序反了会陷入套路陷阱。
Five Steps · Climbing Stairs
dp[i] = 爬到第 i 阶的方法数。状态定义决定了后面全部——常见两种句式："以 i 结尾"（子数组类）与"前 i 个"（子序列/背包类）。
最后一步只有爬 1 或爬 2 阶：dp[i] = dp[i−1] + dp[i−2]。转移 = 枚举最后一步的所有可能，把大问题拆到已定义的子状态。
dp[0]=1（站在地面算一种"不动"），dp[1]=1。边界错 = 全错，且往往不报错只出怪数字。
dp[i] 依赖更小的 i → 从小到大。规则：保证算 dp[i] 时它依赖的状态已算好（背包的倒序就是这条规则的反向应用）。
dp[n]。有的题要 max(dp)（最大子数组和），有的要 dp 最后一位——由状态定义自然决定，不要硬背。
// 爬楼梯（LC 70）完整五步落地 func climbStairs(n int) int { // ③ 初始化（含滚动优化：只留两个变量） prev, cur := 1, 1 // dp[0], dp[1] for i := 2; i <= n; i++ { // ②④ 转移 + 顺序 prev, cur = cur, prev+cur } return cur // ⑤ } // O(n) 时间 · O(1) 空间 // 状态依赖只有前两项 → 滚动变量
DAG View
Linear DP · LC 70/198/53
// 打家劫舍（LC 198）：不相邻取最大 // dp[i] = 前 i 间房能偷的最大金额 func rob(nums []int) int { prev, cur := 0, 0 // dp[i-2], dp[i-1] for _, x := range nums { prev, cur = cur, max(cur, prev+x) // 不偷 i → cur；偷 i → prev+x } return cur } // 最大子数组和（LC 53）：Kadane // f[i] = 以 i 结尾的最大子数组和 func maxSubArray(a []int) int { best, f := a[0], a[0] for i := 1; i < len(a); i++ { f = max(a[i], f+a[i]) // 接 or 重新开 best = max(best, f) } return best }
"前 i 间"的 dp 只依赖前两项 → 滚动成两个变量 O(1) 空间。环形版（213 首尾相连）：拆成"不偷首"与"不偷尾"两个线性问题取大——化环为直的经典技巧。
"子数组必须连续"——只有"以 i 结尾"的状态才能接上 a[i]（子数组类题的标配句式）。全局答案用 best 旁路记录（二叉树 deck 直径题同款手法）。
max(a[i], f+a[i])：要么"重新开一个子数组"，要么"接在前一段后面"——枚举最后一步在这里就是"这个元素归不归前一段管"。
70 爬楼梯 · 198/213 打家劫舍 · 53/152 最大子数组与乘积 · 746 最小花费爬楼梯 · 122 买卖股票最佳时机 II（贪心可解）——共性：一维状态、常数依赖。
LIS · LCS
// LIS（LC 300）：O(n²) 版 // dp[i] = 以 i 结尾的最长递增子序列长度 func lengthOfLIS(a []int) int { dp := make([]int, len(a)) best := 0 for i := range a { dp[i] = 1 for j := 0; j < i; j++ { if a[j] < a[i] && dp[j]+1 > dp[i] { dp[i] = dp[j] + 1 } } best = max(best, dp[i]) } return best } // O(n log n) 版：tails[k] = 长度 k+1 的 // 递增子序列的最小结尾，逐个 lower_bound // 替换（详见二分 deck QA12）
O(n²)："以 i 结尾"——转移必须知道结尾值才能比较；O(n log n)："长度为 k 的最小结尾"——tails 单调，可二分。同一个问题、两种状态设计，复杂度差一个 log——状态定义水平决定复杂度的活教材。
dp[i][j] = a 前 i 个与 b 前 j 个的 LCS 长度：尾字符相等 → dp[i−1][j−1]+1；不等 → max(dp[i−1][j], dp[i][j−1])。O(mn) 时间空间，滚动数组压到 O(min(m,n))。
子序列可不连续 → 状态是"前 i 个"；子数组必须连续 → 状态是"以 i 结尾"。选错句式，转移写不出来——这是 DP 题的第一检查点。
编辑距离（72，双串 DP 之王）、最长回文子序列（516）、俄罗斯套娃（354：W 升 H 降 + LIS）、最大整除子集（368）。
0/1 Knapsack · Rolling Array
Knapsack Family · LC 416/322/518/377
dp[i][c] = max(dp[i−1][c], dp[i−1][c−w]+v)；一维倒序。416 分割等和子集：和为 sum/2 的可行性（bool 背包），是"能否装满"的标准问法。
一维正序。322 零钱兑换（最少硬币：求 min，初始化 +∞）、518 零钱兑换 II（组合数：外层物品内层容量）。
外层物品、内层容量 → 组合（1,2 与 2,1 算一种，518）；外层容量、内层物品 → 排列（算两种，377 组合总和Ⅳ）。两行代码之差，语义完全不同——面试经典陷阱。
① 有没有"选或不选"的资源约束（容量/和/天数）；② 每件能用几次；③ 问可行性/最值/方案数哪一种。三问定位到具体变体。
| 变体 | 遍历 | 代表题 |
|---|---|---|
| 01 可行性 | 倒序 | 416 分割等和子集 M |
| 01 方案数 | 倒序 | 494 目标和 M |
| 完全最值 | 正序 | 322 零钱兑换 M · 279 完全平方数 M |
| 完全组合数 | 物→容 | 518 零钱兑换 II M |
| 完全排列数 | 容→物 | 377 组合总和Ⅳ M · 139 单词拆分 M |
| 分组/二维费用 | 组间正序 | 1155 掷骰子 N 种方法 M |
Top-Down vs Bottom-Up
// 记忆化搜索（自顶向下） var memo map[int]int func dfs(n int) int { if n <= 1 { return 1 } if v, ok := memo[n]; ok { return v } v := dfs(n-1) + dfs(n-2) memo[n] = v return v } // 与递推（自底向上）完全等价 // —— 只是计算顺序相反
① 状态转移是树形/图形难以线性枚举（树 DP、博弈 DP）；② 合法状态集稀疏（递推会算大量无用状态）；③ 转移写"从哪来"比"到哪去"顺（区间 DP）。
① 状态是规整网格（线性/背包/双串）——循环无浪费、可滚动优化空间；② 需要空间 O(1) 滚动；③ 避免递归栈（n 大时）。
记忆化 ↔ 递推一一对应：dfs(i) ↔ dp[i]，递归出口 ↔ 初始化，返回处 ↔ 遍历计算，memo 查表 ↔ 数组直读。先写记忆化再翻递推是稳妥的解题路径。
记忆化用 map 或切片（状态可哈希即可）；闭包里写 dfs 注意先声明 var；大 n 的树形递归留意 goroutine 栈（Go 栈可增长但深递归仍有成本）。
Optimization · Pitfalls
dp[i] 只依赖 dp[i−1] → 两行交替；只依赖常数个前驱 → 常数个变量（爬楼梯、打家劫舍）；二维依赖上一行 → 一行 + 正确的遍历方向（背包）。
集合当状态：dp[mask] 位掩码表示"访问过的城市集合"，TSP O(2ⁿ·n²)。n≤20 的信号词 + " visited/用过"语义 → 想到位压。
求 min 时 dp 要初始化 +∞（且起点为 0）；求方案数时 dp[0]=1（"什么都不选"是一种方案）。初始化即边界条件，错了全盘错。
01 背包正序 → 变完全背包；求组合写成排列序。每次写完背包，默念"方向对不对、谁在外层"。
股票题只记"第 i 天"不够——还要"是否持股/冷却/次数"：状态少一个维度，转移就互相污染。无后效性检查就是查这个。
| 信号 | 反应 |
|---|---|
| 子数组/连续 | "以 i 结尾" + 全局 best 旁路 |
| 子序列/前 i 个 | "前 i 个" + 内层枚举 j |
| 双串 | 二维 dp[i][j]，LCS/编辑距离家族 |
| 选与不选+容量 | 背包三问（重复性/问法/遍历序） |
| n ≤ 20 + 集合 | 状态压缩位掩码 |
| 区间合并类 | 区间 DP：枚举分割点（516/312） |
LeetCode Shortlist
| 族群 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 线性 | 70 爬楼梯 E · 198/213 打家劫舍 M · 53/152 最大子数组 M · 746 最小花费 E | 五步法练手；213 化环为直 |
| 子序列 | 300 LIS M · 1143 LCS M · 72 编辑距离 H · 516 回文子序列 M | 300 双状态观；72 双串之王 |
| 背包 | 416 M · 494 M · 322 M · 518 M · 377 M · 139 单词拆分 M | 三问定位变体；139 是字符串+完全背包 |
| 网格 | 62 不同路径 M · 64 最小路径和 M | 网格 = 二维线性 DP |
| 状态机 | 121/122/309 买卖股票家族 M · 198 变体 | 持股/冷却状态维度 |
| 位压/区间 | 516 回文 M · 312 戳气球 H · 847 访问所有节点 H | 进阶：区间 DP 与 TSP |
Cheat Sheet
| 步骤 | 要回答的唯一问题 | 高频坑 |
|---|---|---|
| ① 状态定义 | 用哪几个参数才能完整描述"当前处境"？ | 漏维度 → 违反无后效性 |
| ② 转移方程 | 枚举"最后一步"的所有可能，取 max/min/求和 | 漏掉一种选择 |
| ③ 初始化 | 最小状态（dp[0] / dp[0][0]）的值是多少？ | 求 min 要 +∞；求方案数 dp[0]=1 |
| ④ 遍历顺序 | 算 dp[i] 时，它依赖的状态都已算好了吗？ | 背包方向、组合/排列序 |
| ⑤ 返回值 | 是 dp[n] 还是 max(dp)？ | 由状态定义自然决定，别硬背 |
| 族 | 状态定义句式 | 代表题 |
|---|---|---|
| 线性 | dp[i] = 前 i 个 / 以 i 结尾的最优值 | 70 爬楼梯 · 198 打家劫舍 · 53 最大子数组和 |
| 子序列 / 双串 | dp[i][j] = a 前 i 个与 b 前 j 个的关系 | 300 LIS · 1143 LCS · 72 编辑距离 |
| 背包 | dp[c] = 容量 c 下的最优值/方案数 | 416 等和子集 · 322 零钱兑换 · 518 兑换 II |
| 场景 | 顺序 |
|---|---|
| 01 背包（每件一次） | 容量 c 倒序——保证读到的是"上一轮"的值 |
| 完全背包（可重复选） | 容量 c 正序——故意让同一件被叠加选取 |
| 组合数（518，1+2 与 2+1 算一种） | 外层物品、内层容量 |
| 排列数（377，1+2 与 2+1 算两种） | 外层容量、内层物品 |
1 · 状态完备吗？如果发现"未来的决策还要看我是怎么走到这一步的"，说明状态漏了信息——把"怎么来的"升级成状态的一个新维度。
2 · 初始化对吗？求最小值初始化 +∞、起点置 0；求方案数 dp[0]=1（"什么都不选"也是一种方案）。
3 · 方向和内外层对吗？背包写完必查：容量倒序还是正序？谁在外层？——这两处决定它是 01 还是完全、是组合还是排列。
4 · 小规模对表了吗？n=1..5 手算一遍和暴力递归对照。DP 出错 90% 在初始化或边界，且不报错只出怪数字。
Interview QA · Part 1
先自答，再对照：每题先说出你的答案（哪怕只说关键词），再展开下面那行——卡住的那 30 秒才是真正长记性的部分。
重叠子问题（值得记忆化）、最优子结构（子最优能拼出原最优）、无后效性（状态不含路径历史）。三者缺一：分别退化成暴力、不可拆、状态污染。
把"缺失的历史"塞进状态维度：股票加"是否持股"、带冷却加"冷冻天数"、访问集合加"位掩码"。状态完备 = 无后效性成立。
子数组/连续段 → "以 i 结尾"（新元素必须挂上）；子序列/计数 → "前 i 个"（新元素可选可不选）。选错的症状：转移方程写不出来。
倒序保证 dp[c−w] 读到的是"上一行"（未考虑物品 i）的值；正序读到本行已更新的值 → 同一物品叠加选取（那正是完全背包）。
是。同一张 DAG：记忆化从目标往回走（自顶向下），递推从边界往前走（自底向上）。选型看状态稀疏度和是否需要滚动优化。
DP 保留所有选择、贪心每步只留一个。敢用贪心的条件：能证明局部最优蕴含全局最优（交换论证）——证明不出来就老实 DP。
同一个问题的两个阶段：裸递归 O(2ⁿ)（重叠子问题被重复算）；加记忆化/递推后 O(n)。"DP = 暴力递归 + 缓存"在这里具象化。
子数组连续，只有"以 i 结尾"的状态才能转移到 i+1（决定接不接）；全局答案用 best 另存。若定义"前 i 个的最大子数组"则转移根本写不出。
Interview QA · Part 2
先自答，再对照。这一组重点在"方向"——01 与完全、组合与排列，差别都只在一行遍历顺序上。
正序时 dp[c−w] 已包含"本轮选过物品 i"的信息 → 再选 i 合法（无限件）。与 01 背包只差一个方向——两套语义共用一个数组。
外层物品内层容量：同一物品集合只有一种计入顺序 → 组合数；外层容量内层物品：不同顺序分别计数 → 排列数。这题是"遍历序即语义"的铁证。
求最小值的转移是 min——初始值必须是"不变坏的上界"（+∞），dp[0]=0 是唯一合法起点；转移时防 +∞+1 溢出可先判 dp[c−w] 可达。
换状态定义：tails[k] = 长度 k+1 的 LIS 最小结尾（单调递增）→ 每个元素 lower_bound 替换 O(log n)。不是优化原状态，是重新设计状态。
首尾不能同偷 → 拆成 [0..n−2] 和 [1..n−1] 两个线性问题取 max。环形约束的通用套路：枚举"断开点"或"首状态"。
每天两种状态：持股/不持股（309 加冷却、714 加手续费）。转移就是状态机边：买/卖/不动。无后效性要求把"能不能卖"编码进状态。
① 贪心可证明 → O(n) 更优（122 股票）；② 双指针/滑动窗口能维持性质 → O(n)（11 盛水）；③ 二分答案 → log×线性。先找更聪明的结构，DP 是兜底大杀器。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch14/15（DP 与高级 DP）· 算法导论第 3 版 ch15 | 最优子结构/重叠子问题形式化、LCS/背包标准分析 |
| LeetCode 70/198/53/300/1143/416/322/518/377 题解 | 各族代表题与遍历序论证 |
| oi-wiki.org/dp · 背包九讲（dd_engi） | 背包分类（01/完全/分组）与遍历序的中文权威 |
| Bellman (1950s) · Dynamic Programming | DP 概念起源（"dynamic"是当时的营销词） |