动态规划
本章题海战术
动态规划
🎯 面试现场还原
面试官：
简单说说你对动态规划的理解，以及解题的一般思路？
候选人：
好的面试官。动态规划本质是空间换时间的算法优化思想，专门解决有「重叠子问题、最优子结构」的问题。
它和暴力递归最大的区别是：会把算过的子问题结果存起来，避免重复计算；和贪心的区别是，DP 每一步都会综合所有前置状态得到全局最优，而贪心只选当前局部最优，不一定能得到全局最优解。
我平时做 DP 题固定四步走：先定义 dp 数组的含义，再推导状态转移方程，然后初始化边界条件，最后确定遍历顺序就能写代码了。写完基础版我一般还会做一轮空间优化。
📌 核心判断标准：DP 三大特性
满足这三个特征的题，基本都可以用动态规划解：
- 重叠子问题：不同的大问题，会重复计算同一个更小的子问题
- 最优子结构：大问题的最优解，可以由子问题的最优解推导而来
- 无后效性：某个状态一旦确定，后续状态的变化不会反过来影响它
💡 补充两种实现方向：
- 自顶向下：递归 + 记忆化数组，思路直观但有递归栈开销
- 自底向上：迭代从边界往上推，也就是常规 DP 代码，面试优先写这种
🧭 标准解题流程（流程图）
📚 经典高频题 详细解题拆解
1. 入门必刷：爬楼梯（LeetCode 70. 简单）
题目描述：爬 n 阶楼梯，每次可以爬 1 或 2 个台阶，求总共有多少种不同的方法爬到楼顶。
完整解题四步走：
- 状态定义：
dp[i]表示爬到第 i 阶楼梯，总共有dp[i]种方法 - 状态转移推导：
到达第 i 阶只有两种合法路径：从 i-1 阶爬 1 步、从 i-2 阶爬 2 步，总方法数为两者之和dp[i] = dp[i-1] + dp[i-2] - 边界初始化：第 1 阶 1 种方法，第 2 阶 2 种方法：
dp[1]=1、dp[2]=2 - 遍历顺序：当前状态依赖前两个状态，从前往后正序遍历
核心代码：
// 基础版：时间O(n) 空间O(n)
public int climbStairs(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// ✅ 技术亮点：滚动数组空间优化 空间O(1)
// 观察到dp[i]只和前两个状态有关，无需保存整个数组
public int climbStairsOpt(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2, cur = 0;
for (int i = 3; i <= n; i++) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return cur;
}2. 网格 DP 经典：最小路径和（LeetCode 64. 中等）
题目描述：给定 m×n 的非负整数网格，从左上角走到右下角，每次只能向右或向下走，求路径上数字总和的最小值。
完整解题四步走：
- 状态定义：
dp[i][j]表示从左上角走到坐标(i,j)时，最小的路径和 - 状态转移推导：
只能向右 / 向下移动，到达 (i,j) 只能来自正上方或正左方，取较小值加当前格子数值dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j] - 边界初始化：
- 第一行只能一直向右走，前缀累加：
dp[0][j] = dp[0][j-1] + grid[0][j] - 第一列只能一直向下走，前缀累加：
dp[i][0] = dp[i-1][0] + grid[i][0]
- 遍历顺序：逐行从左到右遍历，保证计算当前格时，上方和左方都已计算完成
核心代码：
// 基础版：时间O(mn) 空间O(mn)
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// 初始化第一行
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
// 初始化第一列
for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
// 填充dp数组
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
// ✅ 技术亮点：原地修改优化 空间O(1)
// 直接复用原grid数组存储dp结果，不额外开辟空间
public int minPathSumOpt(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j - 1];
for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}3. 双串 DP 标杆：最长公共子序列（LeetCode 1143. 中等）
题目描述：给定两个字符串，返回它们最长公共子序列的长度（子序列不要求连续，保持相对顺序即可）。
完整解题四步走：
- 状态定义：
dp[i][j]表示字符串 1 的前 i 个字符、字符串 2 的前 j 个字符，最长公共子序列的长度 - 状态转移推导：
字符匹配：
s1[i-1] == s2[j-1]时，长度 = 前 i-1 和 j-1 的结果 + 1dp[i][j] = dp[i-1][j-1] + 1
字符不匹配：丢弃其中一个字符串的当前字符，取最大值
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
💡 小技巧：dp 数组下标从 1 开始，字符串下标从 0 开始，天然规避边界越界问题
- 边界初始化：空串与任何字符串的公共子序列长度为 0，Java 数组默认初始化为 0，无需手动赋值
- 遍历顺序：两个字符串均从前往后，逐行逐列填充
核心代码：
// 标准DP版 时间O(mn) 空间O(mn)
public int longestCommonSubsequence(String text1, String text2) {
char[] s1 = text1.toCharArray(), s2 = text2.toCharArray();
int m = s1.length, n = s2.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// ✅ 技术亮点：一维滚动数组优化 空间O(n)
// 用prev变量暂存左上角值，避免一维数组覆盖丢失dp[i-1][j-1]
public int longestCommonSubsequenceOpt(String text1, String text2) {
char[] s1 = text1.toCharArray(), s2 = text2.toCharArray();
int m = s1.length, n = s2.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (s1[i - 1] == s2[j - 1]) {
dp[j] = prev + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
prev = temp;
}
}
return dp[n];
}4. 线性 DP 经典：打家劫舍（LeetCode 198. 中等）
题目描述：沿街房屋藏有现金，相邻房屋不能同时偷窃，求一夜能偷到的最高金额。
完整解题四步走：
- 状态定义：
dp[i]表示前 i 间房屋，能偷窃到的最高金额 - 状态转移推导：
第 i 间房有两种选择：
偷：第 i-1 间不能偷，总金额 = 前 i-2 间最高金额 + 当前房屋金额
不偷：总金额 = 前 i-1 间最高金额
取两者最大值：
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1])
- 边界初始化：0 间房收益为 0，1 间房收益为房屋金额：
dp[0]=0、dp[1]=nums[0] - 遍历顺序：从前往后正序遍历
核心代码：
// 基础版 时间O(n) 空间O(n)
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.length];
}
// ✅ 技术亮点：双变量滚动优化 空间O(1)
// 仅依赖前两个状态，用两个变量替代整个数组
public int robOpt(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int cur = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}5. 完全背包模板：零钱兑换（LeetCode 322. 中等）
题目描述：给定无限数量的不同面额硬币，求凑成总金额所需的最少硬币个数，无法凑成返回 - 1。
完整解题四步走：
- 状态定义：
dp[j]表示凑成金额 j，所需的最少硬币个数 - 状态转移推导：
对每个硬币，选或不选，取最小值：dp[j] = Math.min(dp[j], dp[j - coin] + 1) - 边界初始化：
凑 0 元需要 0 个硬币：dp[0] = 0
其余位置初始化为amount+1（大于理论最大值，代表初始不可达，方便取 min） - 遍历顺序：
硬币数量无限属于完全背包，背包容量正序遍历；外层遍历硬币，内层遍历金额
核心代码：
// 完全背包标准解法 时间O(amount * coins.length) 空间O(amount)
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
// 完全背包核心：容量正序遍历，允许硬币重复选取
for (int j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}6. 背包鼻祖：01 背包（模板题）
题目描述：n 件物品，每件重量 weight [i]、价值 value [i]，只能选一次，背包容量 m，求能装的最大价值。
完整解题四步走：
- 状态定义：
dp[j]表示背包容量为 j 时，能装的最大价值 - 状态转移推导：每件物品选或不选，取最大值
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]) - 边界初始化：
dp[0] = 0，其余初始为 0（求最大值，初始值不影响结果） - 遍历顺序：外层遍历物品，内层倒序遍历容量—— 保证每件物品只被选一次，避免重复累加
核心代码：
// 一维滚动数组模板 空间O(m)
public int zeroOneBag(int[] weight, int[] value, int m) {
int[] dp = new int[m + 1];
for (int i = 0; i < weight.length; i++) {
// 01背包核心：倒序遍历容量，防止物品重复选取
for (int j = m; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[m];
}⚠️ 技术难点与解决方案对照表
| 常见技术难点 | 对应解决方案 | 高频易错场景 |
|---|---|---|
| 状态定义模糊，找不到 dp 数组物理含义 | 固定原则：题目问什么，dp 就定义什么；优先用「前 i 个」「以 i 结尾」两种经典定义 | 最长递增子序列、子数组类题目 |
| 状态转移方程推导不全，漏分支 | 倒推法：枚举所有能到达当前状态的前置路径，列全所有可能再取最值 / 求和 | 打家劫舍、路径类、股票类题目 |
| 背包类正序 / 倒序遍历搞混 | 死记规则：01 背包一维必须倒序（防重复），完全背包必须正序（允许多选）；求组合数外层物品内层容量，求排列数外层容量内层物品 | 零钱兑换、分割等和子集、组合总和 Ⅳ |
| 双串 DP 下标对应错误、数组越界 | 统一用「dp [i][j] 表示前 i 个、前 j 个」的定义，字符串对应下标统一减 1，遍历从 1 开始 | 最长公共子序列、编辑距离 |
| 初始化值错误，导致最值计算异常 | 求最大值初始化为 0 / 最小值，求最小值初始化为无穷大；单独验证空串、0 个物品、0 容量等边界 | 零钱兑换、最小路径和 |
| 空间优化无从下手 | 通用判断：只和上一行有关→降一维；只和前 1-2 个状态有关→用变量滚动替代数组 | 所有线性 DP、网格 DP、背包类题目 |
📝 LeetCode 高频考题分级清单
🌱 入门级（校招 / 基础面必刷，掌握 DP 核心思想）
- 70.爬楼梯
- 509.斐波那契数
- 746.使用最小花费爬楼梯
- 392.判断子序列
🔥 进阶级（社招 / 大厂核心高频，必须能手撕）
- 62.不同路径
- 64.最小路径和
- 198.打家劫舍
- 213.打家劫舍 II
- 300.最长递增子序列
- 1143.最长公共子序列
- 416.分割等和子集（01 背包变种）
- 322.零钱兑换（完全背包）
- 279.完全平方数
- 221.最大正方形
🏆 困难级（拔高加分项，大厂 SP / 终面常考）
- 72.编辑距离
- 123.买卖股票的最佳时机 III
- 188.买卖股票的最佳时机 IV
- 312.戳气球（区间 DP）
- 387.鸡蛋掉落
- 10.正则表达式匹配
- 516.最长回文子序列
💡 面试加分小技巧
回答完基础解法后，可以主动补一句：「我做 DP 题有个习惯，写完基础解法一定会先验证边界 case，再做空间优化。比如大部分线性 DP 和背包问题都能降到 O (1) 或 O (n) 空间，在大数据量场景下能显著降低内存占用。」
真实面试模拟
真实面试模拟
面试官 👨💻：
“同学你好，看你简历写了熟悉常用算法，那我们聊聊动态规划吧。先不着急写题，你能用两三句话说清楚动态规划的核心思想吗？”
候选人 🙋♂️：
“好的。动态规划的核心是将大问题拆解为重叠的子问题，通过记忆化存储子问题的解，避免重复计算，并利用状态转移方程递推出最终答案。关键在于找到状态定义和状态转移，通常用数组或哈希表做缓存，空间上还能进一步优化。”
面试官 👍：
“总结得不错。那接下来咱们直接上题，边写边讲——就用经典的『爬楼梯』热热身吧。假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶，有多少种不同的方法可以爬到楼顶？”
候选人 🙋♂️：
“好的。我先定义 dp[i] 为爬到第 i 阶的方法数，因为最后一步只能从 i-1 或 i-2 跨上来，所以状态转移：
dp[i] = dp[i-1] + dp[i-2]基础情况 dp[0]=1, dp[1]=1。我先写个自底向上的数组版本。”
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];
}面试官 💬：
“可以，但这用了 O(n) 的空间，还能再优化吗？”
候选人 🎯：
“能，dp[i] 只依赖前两个值，用滚动变量替换数组就能 O(1) 空间。滚动更新的核心是保留 prev2 和 prev1。”
public int climbStairs(int n) {
int prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}面试官 👍：
“滚动变量优化很扎实。那我们换个实际点的场景：打家劫舍，相邻房屋不能同时偷，怎么求最大金额？”
候选人 🏠：
“状态 dp[i] 表示到第 i 间房能偷到的最高金额。对第 i 间有两种决策：
- 不偷 i：金额 =
dp[i-1] - 偷 i：金额 =
nums[i] + dp[i-2]
取最大值，再滚动优化到 O(1)。”
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, num + prev2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}面试官 🤔：
“如果房屋是环形的，首尾相邻，你怎么办？”
候选人 🔄：
“拆成两个线性问题：要么不偷第一家，要么不偷最后一家，取两者最大值就行。这利用了问题分解的思想。”
public int robCircle(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(robRange(nums, 0, nums.length-2),
robRange(nums, 1, nums.length-1));
}
private int robRange(int[] nums, int l, int r) {
int prev2 = 0, prev1 = 0;
for (int i = l; i <= r; i++) {
int curr = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}面试官 🧐：
“环形拆成两个线性的思维不错。再来道二维题：一个 m×n 网格，从左上到右下，每次只能向右或向下走，有多少条不同路径？”
候选人 🗺️：
“dp[i][j] 表示到达 (i,j) 的路径数，只能从左边或上边转移：
dp[i][j] = dp[i-1][j] + dp[i][j-1]边界都是 1。我可以先画个转移示意图。”
“空间可以降维到 O(n)，用一维滚动数组：因为每个格子只依赖上一行和左边的值，dp[j] 累加 dp[j-1] 即可。”
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}面试官 😏：
“好，二维降一维的优化很到位。再来个需要‘巧妙定义状态’的：求最长递增子序列的长度（LIS），比如 [10,9,2,5,3,7,101,18] 答案是 4。”
候选人 🔍：
“这题定义 dp[i] 为以 nums[i] 结尾的 LIS 长度是关键。然后遍历 i 前面的 j，如果 nums[j] < nums[i]，就可以接在后面：
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}时间复杂度 O(n²)，但还能用贪心+二分优化到 O(n log n)。”
面试官 💡：
“哦？怎么二分优化？”
候选人 📈：
“维护一个 tails 数组，tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素。遍历 nums，用二分查找第一个大于等于 x 的位置，替换或追加，最后 tails 的长度就是答案。”
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = 0, j = size;
while (i < j) {
int m = (i + j) >>> 1;
if (tails[m] < x) i = m + 1;
else j = m;
}
tails[i] = x;
if (i == size) size++;
}
return size;
}面试官 💭：
“最后来道背包变体：零钱兑换，给定硬币面额和总金额，求凑出该金额的最少硬币数，无法凑出返回 -1。”
候选人 💰：
“完全背包求最小值，状态 dp[w] 为凑出金额 w 的最少硬币数。初始化 dp[0]=0，其他为一个极大值。对每个金额遍历硬币：
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);
dp[0] = 0;
for (int w = 1; w <= amount; w++) {
for (int coin : coins) {
if (w >= coin) {
dp[w] = Math.min(dp[w], dp[w-coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}注意正序循环是允许同一硬币重复使用的，这正是完全背包的标志。”
面试官 🤓：
“几道题下来，你自己觉得动态规划题目的技术难点主要在哪？”
候选人 📝：
“我整理过一张表，正好可以分享出来：”
| 难点 | 常见错误 | 解决方法 |
|---|---|---|
| 状态定义模糊 | 定义成全局最优，导致无法递推 | 明确“以 i 结尾”“前 i 个”等，紧扣问题的规模变量 |
| 空间优化时索引混乱 | 滚动变量更新顺序错误 | 先更新最远的旧值，或用临时变量；画图验证依赖 |
| 背包循环顺序反 | 0-1 背包正序导致物品重复使用 | 完全背包正序，0-1 背包逆序；记住组合数外层物品 |
| 初始化边界值 | 求最小值设为 -1 或 0 | 求最小用 INF，求最大用 -INF，dp[0] 看实际含义 |
| 无法识别题型 | 把区间 DP 当线性 DP 硬做 | 多刷经典母题，建立题型特征映射 |
面试官 👌：
“总结得很到位。那你最后再跟我快速过一下，面试常考的 DP 题型有哪些？”
候选人 🗂️：
“常见大概六类：”
| 类型 | 题目特征 | 代表题 | LeetCode 题号 |
|---|---|---|---|
| 线性 DP | 一维序列，每个位置有选择 | 打家劫舍、爬楼梯 | 198, 70 |
| 路径 DP | 网格，向右/下移动 | 不同路径、最小路径和 | 62, 64 |
| 子序列 DP | 不要求连续，常结合双指针/二分 | 最长递增子序列 | 300 |
| 字符串 DP | 两个字符串的匹配/编辑 | 编辑距离、最长公共子序列 | 72, 1143 |
| 背包问题 | 容量限制，物品选/不选 | 零钱兑换、分割等和子集 | 322, 416 |
| 状态机 DP | 有限状态转移（如买卖股票） | 股票系列（含冷冻期） | 188, 309 |
“这些母题吃透，掌握‘状态→转移→初始化→空间优化’四步，大部分 DP 都能应对。”
面试官 😊：
“好的，今天这场 DP 面得很透，从递推、空间压缩、二分优化到题型梳理，我都挺满意的。回去再把区间 DP 和状态机 DP 练练手，二面可能会更深入。今天就到这里，辛苦了。”
候选人 🙏：
“谢谢面试官，收获很多，我会继续刷题巩固！”