动态规划

动态规划 🔥 核心章节

💡 核心要点

动态规划的核心不是背公式，而是学会一套通用的思考流程：面对任何 DP 题，都能从状态定义出发，一步步推出转移方程、初始化、遍历顺序和返回值。掌握这个流程，比刷 100 道题更有用。

什么是动态规划

动态规划（Dynamic Programming, DP）的本质是：把一个大问题拆成若干重叠的子问题，每个子问题只计算一次，把结果存起来复用。

一句话理解：暴力递归 + 记忆化 = DP。你先写出暴力递归，发现很多子问题被反复计算，于是用一个表存起来——这就是 DP 了。

与贪心的区别

贪心算法在每一步做局部最优选择，一旦选了就不回头。DP 则考虑所有子问题的最优组合——当前的最优选择可能依赖于"如果我之前做了不同的选择，现在会怎样"。

判断标准：如果你能证明局部最优一定导致全局最优，用贪心；否则用 DP。

实战感觉：当你发现贪心策略举不出反例，但也证不了对，通常应该用 DP。DP 比贪心更"安全"——它穷举了所有可能的子问题组合，不会因为局部选择而错过全局最优。

与分治的区别

分治也是把问题拆成子问题，但分治的子问题互不重叠（如归并排序的左右两半）。DP 的子问题大量重叠（如斐波那契的 f(3) 被算了无数次）。

快速判断法：画递归树，看子问题有没有重复。重复了就是 DP，不重复就是分治。

两个前提条件

一个问题能用 DP 解，必须同时满足：

重叠子问题：不同的递归分支会反复计算相同的子问题
最优子结构：大问题的最优解可以由子问题的最优解推导出来

⚠️ 无后效性

还有一个隐含条件常被忽略：无后效性——一旦某个子问题的解确定了，它就不会被后续的决策所改变。如果你的状态定义导致"后面的选择会影响前面的状态"，说明状态定义不够完整，需要增加维度。

如何识别 DP 题

面试中拿到一道题，以下信号提示你可能需要 DP：

题目问的是	DP 类型	例子
最大/最小/最长/最短	最优化 DP	最长递增子序列、最小路径和
有多少种方式/方案	计数 DP	爬楼梯、零钱兑换 II
是否可能/能否达到	可行性 DP	分割等和子集、跳跃游戏

排除信号（什么时候不是 DP）

不是所有最优化问题都要 DP，先检查这些"排除信号"：

特征	更可能是
每步的最优选择不依赖后续决策	贪心（如跳跃游戏 II 用贪心更自然）
需要所有方案的具体内容（不只是数量）	回溯/DFS
状态空间是图结构，需要最短路	BFS/Dijkstra
数组上的连续子段问题	优先考虑滑动窗口/前缀和

从暴力到 DP 的思维链

拿到一道新题时，建议按这个链条思考：

1. 先写暴力递归（不考虑效率，只考虑正确性）
2. 画递归树，观察有没有重复子问题
3. 如果有 → 加记忆化（自顶向下 DP）
4. 改写为递推表（自底向上 DP）
5. 尝试空间优化

不要试图一步到位写出递推方程。 先从暴力递归开始，确保逻辑正确，再一步步优化。这个过程在面试中也是加分的——面试官看到你的思维过程，比直接甩出一个转移方程更有说服力。

解题五步法

这是整个 DP 章节最核心的方法论。面对任何 DP 题，都按这五步走：

第一步：定义状态

用一句自然语言说清楚 dp[i]（或 dp[i][j]）到底代表什么。

这是最关键的一步，状态定义错了，后面全错。

思考技巧：问自己"我需要知道哪些信息，才能做出当前位置的决策？"这些信息就是状态的维度。

如果只需要知道"到第 i 个位置为止"的信息 → 一维 dp[i]
如果还需要知道"剩余容量"或"到第 j 个字符为止" → 二维 dp[i][j]
如果还有"当前处于第 k 种状态" → 三维 dp[i][j][k]

"前 i 个" vs "以 i 结尾"——最容易踩的坑

定义方式	含义	答案在哪	适合什么题
`dp[i]` = 前 i 个元素的最优解	第 i 个可选可不选	`dp[n]`	打家劫舍、爬楼梯
`dp[i]` = 以第 i 个结尾的最优解	第 i 个必须选	`max(dp[0..n-1])`	最大子数组和、LIS

选错定义不会让代码报错，但会让你转移方程怎么也推不对。如果你发现推了半天推不出来，先回来检查状态定义。

增加维度的直觉

如果你发现一维状态无法区分某些关键信息（比如"当前持有股票 vs 不持有"、"上一次选了 0 还是 1"），就需要增加一个维度。增维的本质是：让每个子问题的描述足够精确，消除歧义。

第二步：推导转移方程

问自己：dp[i] 可以从哪些更小的状态得到？做了什么决策？

转移方程就是把"决策"翻译成代码。

核心思考法——"最后一步倒推"

不要从头开始想整个过程，而是只看最后一步：

站在位置，思考"到达这里之前的最后一步是什么？"
爬楼梯：最后一步要么跨 1 阶（从来），要么跨 2 阶（从来）
背包：最后一个考虑的物品要么选了，要么没选
字符串：最后一个字符要么匹配了，要么没匹配

这个方法叫**"最后一步"分析法**，几乎适用于所有 DP 题。

三种常见决策模式

模式	转移方程形式	典型题
选/不选	`dp[i] = max(f(选), f(不选))`	打家劫舍、0/1 背包
枚举前驱	`dp[i] = max(dp[j] + ...) for all j`	LIS、完全背包
分支匹配	`if match: dp[i][j] = dp[i-1][j-1] + ...`	LCS、编辑距离

第三步：确定初始化

找到最小的、不能再拆分的子问题，直接赋值。

初始化就是转移方程的"递归基"。

常见模式：

dp[0] = 0 或 dp[0] = 1（空集/起点）
dp[0][j] = ..., dp[i][0] = ...（第一行/第一列）
全部初始化为 Integer.MAX_VALUE 或 Integer.MIN_VALUE（求最小/最大值时）

关键问题：dp 数组长度是 n 还是 n + 1？这取决于你的状态定义是从 0 开始还是从 1 开始。

初始化的验证方法：手算前 2-3 个状态值，看是否和你的预期一致。如果 dp[1] 已经不对了，说明初始化有问题。

💡 初始化常犯的错

计数 DP 忘了 dp[0] = 1（空集是 1 种方案，不是 0 种）
求最小值忘了初始化为极大值，导致 0 被当成最优解
求最小值初始化用了 Integer.MAX_VALUE，但转移时 MAX_VALUE + 1 溢出为负数 → 应该用 MAX_VALUE / 2 或加判断

第四步：确定遍历顺序

原则：计算 dp[i] 时，它依赖的所有状态必须已经算好。

从转移方程的依赖关系反推遍历方向：

依赖 dp[i-1] → 从小到大遍历
依赖 dp[i+1] → 从大到小遍历
依赖 dp[i-1][j-1] → 两层循环都从小到大
0/1 背包一维优化 → 容量从大到小（防止同一物品被重复使用）

画依赖箭头：在 dp 表上画出每个格子依赖哪些格子，箭头指向应该是"从已算好的指向待计算的"。如果发现箭头方向和你的遍历顺序矛盾，就说明顺序错了。

第五步：确定返回值

返回值不一定是 dp[n]：

如果 dp[i] 定义为"前 i 个元素的最优解" → 返回 dp[n]
如果 dp[i] 定义为"以第 i 个元素结尾的最优解" → 返回 max(dp[0..n-1])
双串 DP → 通常返回 dp[m][n]
区间 DP → 通常返回 dp[0][n-1]

用爬楼梯演示五步法

以 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]。

java

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 有两种实现方式，本质相同，形式不同：

记忆化递归（自顶向下）

从大问题出发，递归拆解，用数组或哈希表缓存已计算的子问题。

java

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];
}

优点：思路自然（先想大问题怎么拆），只计算需要的子问题。缺点：递归栈开销，不方便做空间优化。

递推表（自底向上）

从最小子问题出发，逐步填表，直到算出目标。

优点：没有递归栈开销，方便做空间优化。缺点：需要想清楚遍历顺序，可能计算不需要的子问题。

如何选择？

场景	推荐方式	原因
刚开始想思路	记忆化递归	自然、不容易出错
状态空间稀疏（只有少部分子问题被用到）	记忆化递归	不浪费计算
需要空间优化（滚动数组）	递推表	记忆化递归做不了空间优化
面试最终提交	递推表（通常）	代码更短、更清晰

面试建议：先用记忆化递归理清思路，确认状态和转移没问题后，再改写成递推表。面试官会认为你的思维过程很清晰。

演化链路完整示例（以斐波那契为例）

上面三种写法本质是同一问题的 4 个阶段。面试官问“说一下你怎么一步步优化”时，能连贯说出这 4 步会加分：

java

// 阶段 1：暴力递归 — O(2^n) 时间、O(n) 递归栈
// 问题：fib(40) 已经要算几秒，fib(50) 会超时。f(3) 被重复计算了很多次。
int fib1(int n) {
    if (n <= 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}

// 阶段 2：记忆化递归 — O(n) 时间、O(n) 空间（memo + 递归栈）
// 变化：每个状态只计算一次，二次访问直接读表
int fib2(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return helper(n, memo);
}
int helper(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];          // ★ 命中直接返
    memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    return memo[n];
}

// 阶段 3：递推表 — O(n) 时间、O(n) 空间，去掉递归栈
// 变化：反转方向，从小到大填表
int fib3(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 阶段 4：滚动变量 — O(n) 时间、O(1) 空间
// 变化：观察到 dp[i] 只依赖前两个状态，用两个变量滚动
int fib4(int n) {
    if (n <= 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

4 阶段对比表：

阶段	时间	空间	思维难点
66b4力递归	O(2^n)	O(n)	定义递归函数语义（这一步对了后面都是机械动作）
记忆化递归	O(n)	O(n)	识别重叠子问题 → 加 memo
递推表	O(n)	O(n)	反转计算顺序，确定初始值
滚动变量	O(n)	O(1)	观察状态依赖范围，用变量代替数组

面试误区：不要一上来就写阶段 4。面试官看不到你的思路，反而认为你是背题。正确姿势是：口头说“先写阶段 2 记忆化递归”→ 写完后补一句“如果需要可以改成递推表 + O(1) 空间” → 面试官点头你再写。

空间优化技巧

观察依赖范围

空间优化的核心是观察转移方程依赖了多少历史状态：

依赖范围	优化方式	例子
只依赖前 1-2 个状态	用 2-3 个变量滚动	爬楼梯、斐波那契
只依赖上一行	两行数组交替	网格路径、LCS
二维依赖整列	一维数组 + 遍历方向控制	0/1 背包

一维压缩的遍历方向

当把二维 DP 压缩到一维时，遍历方向至关重要：

0/1 背包：容量倒序遍历（保证每件物品只用一次）
完全背包：容量正序遍历（允许重复使用）

何时不做空间优化

如果题目要求输出具体方案（路径、操作序列），需要回溯 dp 表 → 保留完整的二维表。

DP 解题技巧与直觉培养

掌握了五步法后，下面这些技巧能帮你更快地"感觉到"正确的方向。

技巧一：打表找规律

当转移方程不太确定时，先用暴力（递归/枚举）算出前几个小规模的答案，把结果列成表格，观察有没有递推关系。

n=1: 1
n=2: 2
n=3: 3
n=4: 5
n=5: 8
→ 像斐波那契！试试 dp[i] = dp[i-1] + dp[i-2]

这个方法在面试中出奇地实用——与其硬推转移方程，不如先观察规律再验证。

技巧二：dp 数组打印调试

写完代码后，先不要急着提交。打印整个 dp 数组，用一个小测试用例手动验证每个值是否符合你的状态定义。

java

// 调试时加上这行
System.out.println(Arrays.toString(dp));
// 或者二维：
for (int[] row : dp) System.out.println(Arrays.toString(row));

90% 的 DP bug 都能通过打印 dp 表发现。

技巧三：状态定义试错法

如果一种状态定义推不出转移方程，换一种定义再试。常见的替代方案：

推不动的定义	可以试的替代
`dp[i]` = 前 i 个的最优解	`dp[i]` = 以 i 结尾的最优解
`dp[i]` = 从 0 到 i 的最优	`dp[i]` = 从 i 到末尾的最优（反向 DP）
`dp[i]` 只记录一个值	`dp[i][state]` 增加一个状态维度

不要死磕一个状态定义超过 5 分钟，换个思路可能柳暗花明。

技巧四：从递归到递推的机械转换

记忆化递归和递推表是等价的。如果你已经写出了正确的记忆化递归，可以机械地转换为递推：

递归参数 → dp 数组的维度
递归终止条件 → dp 的初始化
递归调用 → dp 的转移方程
递归调用顺序 → 反过来就是遍历顺序

技巧五：边界条件的"哨兵"技巧

很多 DP 题的边界处理很烦人（第一行、第一列、i=0 的特判），可以用哨兵行/列简化：

java

// 加一行一列哨兵，避免边界特判
int[][] dp = new int[m + 1][n + 1];
// 哨兵行/列的值根据需要设为 0 或极值
// 然后双层循环从 1 开始，dp[i][j] 对应原始的 grid[i-1][j-1]

这在网格 DP 和双串 DP 中特别有用。

技巧六：DP 题的"题感"——什么时候该想到 DP

经过大量练习后，你会形成这样的直觉：

看到"最小/最大/最长/方案数" + "不能暴力枚举" → DP
看到"选或不选" + "有限制条件" → 背包
看到两个字符串 → 双串 DP（LCS/编辑距离系列）
看到区间操作（合并/分割） → 区间 DP
看到"轮流操作、先手后手" → 博弈 DP
看到"状态机"（比如带冷冻期的股票） → 状态机 DP
看到 n ≤ 20 且涉及集合选择 → 状压 DP

常见错误与调试方法

错误	症状	调试方法
状态定义模糊	转移方程写不出来，或写出来但结果不对	打印 dp 表，检查每个值是否符合你的自然语言定义
初始化遗漏	dp 表前几个值就不对	手算前 3-5 个值，与 dp 表对照
遍历顺序错误	用到了还没算好的状态，结果偏小或偏大	在转移前打印依赖的状态，确认它们已更新
Off-by-one	数组越界或最后一个状态没算到	明确 dp 数组长度是 n 还是 n+1，画图确认下标范围
忘记特判	WA 在边界 case	检查 n=0、n=1、空数组、单元素等极端情况

面试中 DP 题的沟通策略

先说思路：拿到题后不要直接写代码，先和面试官说"我觉得这是一个 XX 类型的 DP"
说清状态定义：面试官最看重的不是代码，而是你的状态定义和转移方程
小例子验证：用一个 2-3 个元素的小例子走一遍你的五步法，确认正确
先写朴素版本：先写出 O(n²) 或 O(n×m) 的正确版本，再讨论优化
主动提空间优化：如果时间够，主动提出空间优化方案（滚动数组/变量压缩），展示你的深度

DP 题型全景图

掌握了五步法之后，接下来按题型深入。每种类型有自己的状态定义套路和转移模式，但五步法的思考流程是通用的。

类型	核心特征	难度	面试频率	详细页面
线性 DP + 网格 DP	状态沿一维/二维线性推进	⭐⭐	🔥🔥🔥	线性与网格 DP
背包 DP	物品 + 容量限制 + 选择决策	⭐⭐	🔥🔥🔥	背包 DP
序列与回文 DP	字符串匹配、子序列、回文结构	⭐⭐⭐	🔥🔥🔥	序列与回文 DP
区间 DP + 状态机 DP	区间合并分割 / 多状态转移	⭐⭐⭐	🔥🔥	区间与状态机 DP
树形 DP	子树信息汇聚到父节点	⭐⭐⭐	🔥🔥	树形 DP
状压 DP + 计数 DP	集合位掩码 / 方案计数	⭐⭐⭐	🔥🔥	状压与计数 DP
数位 DP	逐位构造，统计 [1,N] 内满足条件的数	⭐⭐⭐	🔥	数位 DP
博弈 DP	两人轮流最优决策，MinMax 思想	⭐⭐⭐	🔥	博弈 DP
概率与期望 DP	随机事件的概率/期望值计算	⭐⭐⭐	💧	概率与期望 DP
DP 优化技巧	单调队列/栈、二分、前缀和优化	⭐⭐⭐	🔥🔥	DP 优化技巧

建议学习顺序

第一阶段（基础，必须掌握）：
  线性与网格 DP → 背包 DP → 序列与回文 DP

第二阶段（进阶，面试常考）：
  区间与状态机 DP → 树形 DP → 状压与计数 DP

第三阶段（高阶，锦上添花）：
  数位 DP → 博弈 DP → 概率与期望 DP → DP 优化技巧

每个阶段的题型都建立在前一阶段的基础之上。比如博弈 DP 用到了区间 DP 的遍历方式，状压 DP 用到了背包的"选/不选"思想。按顺序学事半功倍。

DP 总结速查表

面试前最后复习用的速查表。

状态定义速查

题型	状态定义模式	例子
线性（语义 A）	`dp[i]` = 前 i 个的最优解	打家劫舍
线性（语义 B）	`dp[i]` = 以 i 结尾的最优解	最大子数组和
网格	`dp[i][j]` = 到达 (i,j) 的最优解	最小路径和
背包	`dp[j]` = 容量为 j 时的最优解	分割等和子集
双串	`dp[i][j]` = s 前 i 个 + t 前 j 个的最优解	编辑距离
区间	`dp[i][j]` = 区间 [i,j] 上的最优解	戳气球
状态机	`dp[i][state]` = 第 i 天处于 state 的最优解	股票买卖
树形	`dp[node]` = 以 node 为根的子树的最优解	打家劫舍 III
状压	`dp[mask]` = 已选集合为 mask 时的最优解	Hamilton 路径

转移方程速查

操作类型	转移形式	dp[0] 初始值
求最大值	`max(dp[j], dp[j-w]+v)`	0
求最小值（恰好装满）	`min(dp[j], dp[j-w]+v)`	0（其余 MAX）
方案计数	`dp[j] += dp[j-w]`	1
可行性判断	`dp[j] = dp[j] \|\| dp[j-w]`	true

遍历方向速查

场景	方向	原因
0/1 背包一维	容量倒序	防止同一物品重复使用
完全背包一维	容量正序	允许重复使用
区间 DP	长度从小到大	短区间先算好，长区间才能用
反向 DP（地下城）	从右下到左上	信息从终点流向起点
期望 DP	从目标向起点推	期望值需要逆向传递

动态规划 ​

什么是动态规划 ​

与贪心的区别 ​

与分治的区别 ​

两个前提条件 ​

如何识别 DP 题 ​

排除信号（什么时候不是 DP） ​

从暴力到 DP 的思维链 ​

解题五步法 ​

第一步：定义状态 ​

第二步：推导转移方程 ​

第三步：确定初始化 ​

第四步：确定遍历顺序 ​

第五步：确定返回值 ​

用爬楼梯演示五步法 ​

自顶向下 vs 自底向上 ​

记忆化递归（自顶向下） ​

递推表（自底向上） ​

如何选择？ ​

演化链路完整示例（以斐波那契为例） ​

空间优化技巧 ​

观察依赖范围 ​

一维压缩的遍历方向 ​

何时不做空间优化 ​

DP 解题技巧与直觉培养 ​

技巧一：打表找规律 ​

技巧二：dp 数组打印调试 ​

技巧三：状态定义试错法 ​

技巧四：从递归到递推的机械转换 ​

技巧五：边界条件的"哨兵"技巧 ​

技巧六：DP 题的"题感"——什么时候该想到 DP ​

常见错误与调试方法 ​

面试中 DP 题的沟通策略 ​

DP 题型全景图 ​

建议学习顺序 ​

DP 总结速查表 ​

状态定义速查 ​

转移方程速查 ​

遍历方向速查 ​

动态规划

什么是动态规划

与贪心的区别

与分治的区别

两个前提条件

如何识别 DP 题

排除信号（什么时候不是 DP）

从暴力到 DP 的思维链

解题五步法

第一步：定义状态

第二步：推导转移方程

第三步：确定初始化

第四步：确定遍历顺序

第五步：确定返回值

用爬楼梯演示五步法

自顶向下 vs 自底向上

记忆化递归（自顶向下）

递推表（自底向上）

如何选择？

演化链路完整示例（以斐波那契为例）

空间优化技巧

观察依赖范围

一维压缩的遍历方向

何时不做空间优化

DP 解题技巧与直觉培养

技巧一：打表找规律

技巧二：dp 数组打印调试

技巧三：状态定义试错法

技巧四：从递归到递推的机械转换

技巧五：边界条件的"哨兵"技巧

技巧六：DP 题的"题感"——什么时候该想到 DP

常见错误与调试方法

面试中 DP 题的沟通策略

DP 题型全景图

建议学习顺序

DP 总结速查表

状态定义速查

转移方程速查

遍历方向速查