动态规划
动态规划 🔥 核心章节
💡 核心要点
动态规划的核心不是背公式，而是学会一套通用的思考流程：面对任何 DP 题，都能从状态定义出发，一步步推出转移方程、初始化、遍历顺序和返回值。掌握这个流程，比刷 100 道题更有用。
什么是动态规划
动态规划（Dynamic Programming, DP）的本质是：把一个大问题拆成若干重叠的子问题，每个子问题只计算一次，把结果存起来复用。
与贪心的区别
贪心算法在每一步做局部最优选择，一旦选了就不回头。DP 则考虑所有子问题的最优组合——当前的最优选择可能依赖于"如果我之前做了不同的选择，现在会怎样"。
判断标准：如果你能证明局部最优一定导致全局最优，用贪心；否则用 DP。
与分治的区别
分治也是把问题拆成子问题，但分治的子问题互不重叠（如归并排序的左右两半）。DP 的子问题大量重叠（如斐波那契的 f(3) 被算了无数次）。
两个前提条件
一个问题能用 DP 解，必须同时满足：
- 重叠子问题：不同的递归分支会反复计算相同的子问题
- 最优子结构：大问题的最优解可以由子问题的最优解推导出来
如何识别 DP 题
面试中拿到一道题，以下信号提示你可能需要 DP：
| 题目问的是 | DP 类型 | 例子 |
|---|---|---|
| 最大/最小/最长/最短 | 最优化 DP | 最长递增子序列、最小路径和 |
| 有多少种方式/方案 | 计数 DP | 爬楼梯、零钱兑换 II |
| 是否可能/能否达到 | 可行性 DP | 分割等和子集、跳跃游戏 |
验证方法：尝试写出暴力递归，画递归树。如果发现大量重复节点 → 确认是 DP。
解题五步法
这是整个 DP 章节最核心的方法论。面对任何 DP 题，都按这五步走：
第一步：定义状态
用一句自然语言说清楚
dp[i]（或dp[i][j]）到底代表什么。
这是最关键的一步，状态定义错了，后面全错。
思考技巧：问自己"我需要知道哪些信息，才能做出当前位置的决策？"这些信息就是状态的维度。
- 如果只需要知道"到第 i 个位置为止"的信息 → 一维
dp[i] - 如果还需要知道"剩余容量"或"到第 j 个字符为止" → 二维
dp[i][j] - 如果还有"当前处于第 k 种状态" → 三维
dp[i][j][k]
常见陷阱：dp[i] 表示"前 i 个元素的最优解"和"以第 i 个元素结尾的最优解"是完全不同的定义，会导致完全不同的转移方程。
第二步：推导转移方程
问自己：
dp[i]可以从哪些更小的状态得到？做了什么决策？
转移方程就是把"决策"翻译成代码。
思考方法：站在第 i 个位置，思考"我有哪些选择"：
- 选或不选当前元素 →
dp[i] = max(dp[i-2] + nums[i], dp[i-1]) - 从哪个前驱转移过来 →
dp[i] = min(dp[j] + cost) for all valid j - 匹配或不匹配 →
dp[i][j]根据s[i] == t[j]分两种情况
第三步：确定初始化
找到最小的、不能再拆分的子问题，直接赋值。
初始化就是转移方程的"递归基"。
常见模式：
dp[0] = 0或dp[0] = 1（空集/起点）dp[0][j] = ...,dp[i][0] = ...（第一行/第一列）- 全部初始化为
Integer.MAX_VALUE或Integer.MIN_VALUE（求最小/最大值时）
关键问题：dp 数组长度是 n 还是 n + 1？这取决于你的状态定义是从 0 开始还是从 1 开始。
第四步：确定遍历顺序
原则：计算
dp[i]时，它依赖的所有状态必须已经算好。
从转移方程的依赖关系反推遍历方向：
- 依赖
dp[i-1]→ 从小到大遍历 - 依赖
dp[i+1]→ 从大到小遍历 - 依赖
dp[i-1][j-1]→ 两层循环都从小到大 - 0/1 背包一维优化 → 容量从大到小（防止同一物品被重复使用）
第五步：确定返回值
返回值不一定是 dp[n]：
- 如果
dp[i]定义为"前 i 个元素的最优解" → 返回dp[n] - 如果
dp[i]定义为"以第 i 个元素结尾的最优解" → 返回max(dp[0..n-1]) - 双串 DP → 通常返回
dp[m][n]
用爬楼梯演示五步法
以 LeetCode 70 - 爬楼梯 为例，完整走一遍：
题目：每次可以爬 1 或 2 个台阶，问爬到第 n 阶有多少种方法。
第一步：定义状态dp[i] = 爬到第 i 阶的方法数。
第二步：转移方程 到第 i 阶，要么从第 i-1 阶爬 1 步，要么从第 i-2 阶爬 2 步：
第三步：初始化dp[0] = 1（站在地面，1 种方式），dp[1] = 1（爬 1 阶只有 1 种方式）。
第四步：遍历顺序dp[i] 依赖 dp[i-1] 和 dp[i-2]，从小到大遍历。
第五步：返回值dp[n]。
public int climbStairs(int n) {
if (n <= 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}自顶向下 vs 自底向上
DP 有两种实现方式，本质相同，形式不同：
记忆化递归（自顶向下）
从大问题出发，递归拆解，用数组或哈希表缓存已计算的子问题。
public int climbStairs(int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return dfs(n, memo);
}
private int dfs(int n, int[] memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
return memo[n];
}优点：思路自然（先想大问题怎么拆），只计算需要的子问题。 缺点：递归栈开销，不方便做空间优化。
递推表（自底向上）
从最小子问题出发，逐步填表，直到算出目标。
优点：没有递归栈开销，方便做空间优化。 缺点：需要想清楚遍历顺序，可能计算不需要的子问题。
面试建议：先用记忆化递归理清思路，确认状态和转移没问题后，再改写成递推表。
空间优化技巧
观察依赖范围
空间优化的核心是观察转移方程依赖了多少历史状态：
| 依赖范围 | 优化方式 | 例子 |
|---|---|---|
| 只依赖前 1-2 个状态 | 用 2-3 个变量滚动 | 爬楼梯、斐波那契 |
| 只依赖上一行 | 两行数组交替 | 网格路径、LCS |
| 二维依赖整列 | 一维数组 + 遍历方向控制 | 0/1 背包 |
一维压缩的遍历方向
当把二维 DP 压缩到一维时，遍历方向至关重要：
- 0/1 背包：容量倒序遍历（保证每件物品只用一次）
- 完全背包：容量正序遍历（允许重复使用）
何时不做空间优化
如果题目要求输出具体方案（路径、操作序列），需要回溯 dp 表 → 保留完整的二维表。
常见错误与调试方法
| 错误 | 症状 | 调试方法 |
|---|---|---|
| 状态定义模糊 | 转移方程写不出来，或写出来但结果不对 | 打印 dp 表，检查每个值是否符合你的自然语言定义 |
| 初始化遗漏 | dp 表前几个值就不对 | 手算前 3-5 个值，与 dp 表对照 |
| 遍历顺序错误 | 用到了还没算好的状态，结果偏小或偏大 | 在转移前打印依赖的状态，确认它们已更新 |
| Off-by-one | 数组越界或最后一个状态没算到 | 明确 dp 数组长度是 n 还是 n+1，画图确认下标范围 |
DP 题型全景图
掌握了五步法之后，接下来按题型深入。每种类型有自己的状态定义套路和转移模式，但五步法的思考流程是通用的。
| 类型 | 核心特征 | 详细页面 |
|---|---|---|
| 线性 DP + 网格 DP | 状态沿一维/二维线性推进 | 线性与网格 DP |
| 背包 DP | 物品 + 容量限制 + 选择决策 | 背包 DP |
| 序列与回文 DP | 字符串匹配、子序列、回文结构 | 序列与回文 DP |
| 区间 DP + 状态机 DP | 区间合并分割 / 多状态转移 | 区间与状态机 DP |
| 树形 DP | 子树信息汇聚到父节点 | 树形 DP |
| 状压 DP + 计数 DP | 集合位掩码 / 方案计数 | 状压与计数 DP |