动态规划题型：解题思路与方法
动态规划（DP）在面试中出现率约 20-25%，是失败率最高的题型。但 DP 不是数学题，不需要数学好，需要的是一套可重复的推导流程。
DP 的两个条件
一个问题能用 DP 解，必须同时满足：
- 最优子结构：大问题的最优解可以由小问题的最优解组合而成。比如最短路径、最少硬币、最大利润。
- 重叠子问题：同一个子问题会被重复计算。比如 Fibonacci，算 fib(5) 要算 fib(3)，算 fib(4) 也要算 fib(3)。
判断方法：先写暴力递归，如果递归树里有重复的函数调用，就是重叠子问题。如果题目问”最少/最多/多少种方式”，大概率有最优子结构。
四步推导法
每道 DP 题都走这四步，不管题目长什么样。
第一步：定义状态（最重要）
问自己：dp[i] 代表什么？用一句话写出来。
比如：
- “dp[i] 表示爬到第 i 阶的方法数”
- “dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数”
这一步错了，后面全白搭。写代码前先写英文句子：“dp[i] represents the minimum/maximum/count of X for the first i elements”。
第二步：构造转移方程
问自己：最后一步做了什么选择？
以爬楼梯为例：最后一步要么走 1 阶（前面有 dp[n-1] 种），要么走 2 阶（前面有 dp[n-2] 种）。所以 dp[n] = dp[n-1] + dp[n-2]。
以打家劫舍为例：最后一间房要么偷（dp[n-2] + nums[n]），要么不偷（dp[n-1]）。取最大值 dp[n] = max(dp[n-1], dp[n-2] + nums[n])。
这个问题的核心是：当前状态依赖哪些之前的状态？怎么依赖？
第三步：处理边界
最小子问题是什么？直接能算出来的。
- dp[0] 是什么含义？空输入？第一个元素？
- dp[1] 是什么？
用手动模拟前两三个值验证，确保边界和状态定义一致。最常见的 bug 是 dp[0] 含义混乱——有时表示”空输入”，有时表示”第一个元素”。
第四步：选择方向
| 方式 | 写法 | 优点 | 缺点 |
|---|---|---|---|
| 自顶向下（记忆化） | 递归 + cache | 逻辑直接映射问题 | 递归栈溢出风险，空间难优化 |
| 自底向上（填表） | 迭代填数组 | 无递归开销，可优化空间到 O(1) | 要先想清楚填表顺序 |
面试建议：先用自顶向下写对，再改成自底向上优化空间。填表顺序看依赖方向：如果 dp[i] 依赖 dp[i-1]，从左到右填。
常见 DP 模式
| 模式 | 特征 | 转移方程形状 | 典型题 |
|---|---|---|---|
| 线性 DP | 一维序列，每个状态依赖前几个 | dp[i] = f(dp[i-1], dp[i-2]) | 爬楼梯、Fibonacci、打家劫舍 |
| 硬币找零 | ”达到目标值的最少/多少种方式” | dp[i] += dp[i - coin] | Coin Change、Combination Sum |
| 最长公共子序列 | 两个字符串，“最长公共”或”最少操作” | dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) | LCS、Edit Distance |
| 最长递增子序列 | 序列排序问题，每个元素扩展之前最优 | dp[i] = max(dp[j]) + 1 | LIS |
| 背包 | 每个物品”选或不选” + 容量约束 | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]) | 0/1 Knapsack、Partition Equal |
| 网格 DP | 矩阵上的路径/区域 | dp[i][j] = f(dp[i-1][j], dp[i][j-1]) | Unique Paths、最小路径和 |
| 前缀和 DP | 区间查询用预计算 | prefix[i] = prefix[i-1] + arr[i] | 子数组和 |
识别信号
题目出现这些词，往 DP 想：
- “最少/最多/最优”
- “有多少种方式/方法”
- “能否到达/组成”
- “最长/最短的子序列/子数组”
- “两个字符串的公共/差异”
常见坑
- 跳过状态定义直接写代码：dp[i] 代表什么都没想清楚就开写，转移方程一定错。先写句子，再写代码。
- 背转移方程：能默写 Coin Change 但推不出 Edit Distance。每道题都从状态定义开始推导，不查答案。
- 边界含义混乱：dp[0] 是”空输入”还是”第一个元素”？取决于你的状态定义。手动算前三个值验证。
- 填表顺序错误：dp[i][j] 依赖 dp[i-1][j-1]，必须从左到右、从上到下填。写循环前画依赖箭头。
- 过早优化空间：先把 O(n²) 的二维表写对，验证正确，再压缩成 O(n) 或 O(1)。压缩后 debug 难得多。
- 不 trace 表格：代码跑对了但说不清每个格子为什么是这个值。面试官会让你解释，不能 trace 就没了信心。
解题流程速查卡
1. 读题 → 提取"最优值/计数/能否"关键词 → 判断是否 DP
2. 定义状态 → 用一句话写 "dp[i] 代表..."
3. 问"最后一步什么选择" → 推导转移方程
4. 手动算前三个值 → 确定边界
5. 选自顶向下或自底向上 → 写代码
6. 用示例验证 → trace 表格每个格子
已做过的 DP 题
- 19. Custom Fibonacci Sequence — 线性 DP，dp[n] = dp[n-1] + dp[n-2]
- 20. Ways to Fill Slots with Single or Double Coverage — 爬楼梯变体，dp[n] = dp[n-1] + dp[n-2]
LeetCode 必刷 DP 题
优先刷这些（按难度递增）：
- Climbing Stairs（爬楼梯）
- House Robber（打家劫舍）
- Coin Change（硬币找零）
- Longest Increasing Subsequence（最长递增子序列）
- Longest Common Subsequence（最长公共子序列）
- Edit Distance（编辑距离）
- 0/1 Knapsack / Partition Equal Subset Sum（背包/等和分割）