wehub-resource-sync
269 lines
11 KiB
Markdown
269 lines
11 KiB
Markdown
---
|
|
title: 动态规划面试题总结：状态转移、背包、子序列与 Java 模板
|
|
description: 动态规划面试题总结，讲解状态定义、状态转移、初始化、遍历顺序、0-1 背包、完全背包、子序列、区间 DP 和 LeetCode 高频题。
|
|
category: 计算机基础
|
|
tag:
|
|
- 算法
|
|
head:
|
|
- - meta
|
|
- name: keywords
|
|
content: 动态规划,DP,状态转移,背包问题,0-1背包,完全背包,子序列,区间DP,Java动态规划,LeetCode动态规划
|
|
---
|
|
|
|
动态规划难，不是因为代码一定长，而是因为状态定义一旦错了，后面的转移方程、初始化和遍历顺序都会跟着错。
|
|
|
|
面试里不要一上来就背模板。先问自己两个问题：这个问题能不能拆成子问题？当前答案是否依赖前面已经算过的答案？如果这两个问题都成立，再考虑 DP。
|
|
|
|
## 面试考察重点
|
|
|
|
- 能说清 `dp[i]` 或 `dp[i][j]` 的含义。
|
|
- 能写出状态转移方程。
|
|
- 能处理初始化和遍历顺序。
|
|
- 能判断是否可以压缩空间。
|
|
- 能区分背包、子序列、区间等常见类型。
|
|
|
|
## 什么时候考虑动态规划？
|
|
|
|
DP 不是看到“最值”就套。更靠谱的判断是看两个条件：
|
|
|
|
1. 问题能不能拆成规模更小的同类问题。
|
|
2. 子问题会不会被反复计算。
|
|
|
|
比如斐波那契数列，`f(n)` 依赖 `f(n - 1)` 和 `f(n - 2)`，而 `f(n - 2)` 会在递归里被反复计算。把这些中间结果存下来，就是 DP。
|
|
|
|
面试里可以先从暴力递归说起，再说明哪里重复计算，最后把递归改成记忆化搜索或表格递推。这个过程比直接背 `dp` 数组更容易让面试官相信你真的理解。
|
|
|
|
## DP 五步法
|
|
|
|
1. 定义状态：`dp[i]` 到底表示什么。
|
|
2. 写转移：当前状态从哪些状态推出来。
|
|
3. 做初始化：没有前置状态时答案是什么。
|
|
4. 定遍历顺序：先算哪些状态，后算哪些状态。
|
|
5. 检查样例：用一个小输入手推数组。
|
|
|
|
其中最重要的是第 1 步。`dp[i]` 的含义一旦含糊，后面的代码就会变成试出来的。
|
|
|
|
一个好的状态定义通常满足：
|
|
|
|
- 能覆盖题目要问的答案。
|
|
- 能从更小状态推出来。
|
|
- 维度尽量少，但不要为了省空间把含义写乱。
|
|
|
|
## 一维 DP 示例
|
|
|
|
爬楼梯问题：
|
|
|
|
```java
|
|
int climbStairs(int n) {
|
|
if (n <= 2) {
|
|
return n;
|
|
}
|
|
int prev2 = 1;
|
|
int prev1 = 2;
|
|
for (int i = 3; i <= n; i++) {
|
|
int cur = prev1 + prev2;
|
|
prev2 = prev1;
|
|
prev1 = cur;
|
|
}
|
|
return prev1;
|
|
}
|
|
```
|
|
|
|
状态含义：到第 `i` 阶有多少种走法。转移方程：`dp[i] = dp[i - 1] + dp[i - 2]`。
|
|
|
|
这题还可以从递归推出来：
|
|
|
|
```text
|
|
到第 i 阶的最后一步，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。
|
|
```
|
|
|
|
所以 `dp[i]` 只依赖前两个状态，可以把数组压缩成两个变量。空间压缩的前提是你确认旧状态以后不会再用。
|
|
|
|
## 0-1 背包模板
|
|
|
|
每个物品只能选一次：
|
|
|
|
```java
|
|
int knapsack01(int[] weights, int[] values, int capacity) {
|
|
int[] dp = new int[capacity + 1];
|
|
for (int i = 0; i < weights.length; i++) {
|
|
for (int j = capacity; j >= weights[i]; j--) {
|
|
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
|
|
}
|
|
}
|
|
return dp[capacity];
|
|
}
|
|
```
|
|
|
|
容量要倒序遍历，避免同一个物品在一轮里被重复使用。
|
|
|
|
倒序遍历是 0-1 背包最容易被问的点。假设容量正序遍历，计算 `dp[j]` 时可能用到本轮刚更新过的 `dp[j - weight]`，等于同一个物品被选了多次。这就变成完全背包了。
|
|
|
|
0-1 背包的典型问法不一定直接叫背包，像“能否分成两个和相等的子集”，可以转成：能否从数组里选一些数，使它们的和等于总和的一半。
|
|
|
|
## 完全背包模板
|
|
|
|
每个物品可以选多次：
|
|
|
|
```java
|
|
int unboundedKnapsack(int[] weights, int[] values, int capacity) {
|
|
int[] dp = new int[capacity + 1];
|
|
for (int i = 0; i < weights.length; i++) {
|
|
for (int j = weights[i]; j <= capacity; j++) {
|
|
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
|
|
}
|
|
}
|
|
return dp[capacity];
|
|
}
|
|
```
|
|
|
|
容量正序遍历，允许当前物品被重复使用。
|
|
|
|
完全背包里，正序遍历容量正是为了允许当前物品重复使用。比如零钱兑换，每种硬币可以用多次，计算更大金额时可以基于当前硬币已经参与过的状态继续转移。
|
|
|
|
如果题目问的是“组合数”还是“排列数”，遍历顺序也会变：
|
|
|
|
- 组合数：通常先遍历物品，再遍历容量。
|
|
- 排列数：通常先遍历容量，再遍历物品。
|
|
|
|
这块面试不一定问很深，但遇到零钱兑换 II 这类题时很关键。
|
|
|
|
## 常见题型
|
|
|
|
| 题型 | 状态设计 | 代表题 |
|
|
| --------------- | ------------------------------------------------------ | ------------- |
|
|
| 爬楼梯/打家劫舍 | `dp[i]` 表示前 `i` 个位置的最优值 | 70、198 |
|
|
| 背包 | `dp[j]` 表示容量为 `j` 时的最优值或方案数 | 416、518、322 |
|
|
| 子序列 | `dp[i]` 或 `dp[i][j]` 表示以某位置结尾或两个前缀的答案 | 300、1143 |
|
|
| 回文 | `dp[i][j]` 表示区间 `[i, j]` 是否满足条件或最优值 | 647、516 |
|
|
| 路径 | `dp[i][j]` 表示走到格子 `(i, j)` 的答案 | 62、64 |
|
|
|
|
## 记忆化搜索和递推怎么选？
|
|
|
|
两种写法都在存子问题答案。
|
|
|
|
| 写法 | 特点 | 适合场景 |
|
|
| ---------- | ---------------------------- | -------------------------- |
|
|
| 记忆化搜索 | 从目标状态往下递归，按需计算 | 状态转移复杂、递归更自然 |
|
|
| 递推 | 从小状态往大状态填表 | 遍历顺序清楚、方便压缩空间 |
|
|
|
|
如果一开始想不清遍历顺序，可以先写记忆化搜索。等状态关系清楚后，再改成递推。很多树形 DP、区间 DP，用记忆化搜索更容易写对。
|
|
|
|
## 面试手写路径
|
|
|
|
DP 题不建议直接从代码开始。面试手写时，可以先把下面 4 句话讲清楚：
|
|
|
|
1. `dp` 数组的含义是什么，答案最终落在哪个位置。
|
|
2. 当前状态依赖哪些旧状态，为什么这些旧状态已经算过。
|
|
3. 初始化为什么这样写，尤其是 `0`、`1`、无穷大分别代表什么。
|
|
4. 遍历顺序为什么不会提前使用未计算或不该重复使用的状态。
|
|
|
|
如果这 4 句话说不清，代码大概率是靠记忆写出来的，遇到变体就容易散。
|
|
|
|
## 代表题精讲：零钱兑换
|
|
|
|
[322. 零钱兑换](https://leetcode.cn/problems/coin-change/) 是完全背包里很适合面试的一题。题目给定硬币面额和目标金额，问凑成目标金额最少需要多少枚硬币，每种硬币可以使用无限次。
|
|
|
|
状态定义可以这样说：
|
|
|
|
```text
|
|
dp[j] 表示凑成金额 j 所需的最少硬币数。
|
|
```
|
|
|
|
初始化是这题的关键。`dp[0] = 0`，表示凑成金额 0 不需要硬币；其他金额先设成一个不可能的较大值，表示暂时不可达。
|
|
|
|
代码里用到 `Arrays.fill`，需要导入 `java.util.Arrays`。
|
|
|
|
```java
|
|
int coinChange(int[] coins, int amount) {
|
|
int max = amount + 1;
|
|
int[] dp = new int[amount + 1];
|
|
Arrays.fill(dp, max);
|
|
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] == max ? -1 : dp[amount];
|
|
}
|
|
```
|
|
|
|
为什么容量正序遍历？因为一枚硬币可以用多次。计算 `dp[j]` 时使用 `dp[j - coin]`，如果 `dp[j - coin]` 已经在本轮被当前硬币更新过，就代表当前硬币可以继续被使用，这正好符合完全背包。
|
|
|
|
如果题目变成“每种硬币只能用一次”，容量就要倒序遍历。遍历方向不是格式问题，而是在控制同一件物品能不能重复参与转移。
|
|
|
|
## 状态定义对比
|
|
|
|
DP 题经常不是不会写转移，而是状态含义选错。下面几组状态看起来接近，但写法完全不同：
|
|
|
|
| 题型 | 状态含义 | 常见转移关注点 |
|
|
| -------------- | ---------------------------------------- | ------------------------------ |
|
|
| 最长递增子序列 | `dp[i]` 表示以 `nums[i]` 结尾的 LIS 长度 | 必须选 `nums[i]`，向前找更小值 |
|
|
| 打家劫舍 | `dp[i]` 表示前 `i` 间房子的最大金额 | 第 `i` 间偷或不偷 |
|
|
| 最长公共子序列 | `dp[i][j]` 表示两个前缀的 LCS 长度 | 比较两个前缀最后一个字符 |
|
|
| 回文子串 | `dp[i][j]` 表示区间 `[i, j]` 是否回文 | 依赖内部区间 `[i + 1, j - 1]` |
|
|
|
|
面试里可以主动说一句：这里的 `dp[i]` 是“以 i 结尾”，不是“前 i 个元素里的最优值”。这句话能避免很多子序列题写错。
|
|
|
|
## 过程示意和边界样例
|
|
|
|
以爬楼梯为例，`n = 5` 时的状态变化如下：
|
|
|
|
| `i` | `dp[i - 2]` | `dp[i - 1]` | `dp[i]` |
|
|
| --- | ----------- | ----------- | ------- |
|
|
| 3 | 1 | 2 | 3 |
|
|
| 4 | 2 | 3 | 5 |
|
|
| 5 | 3 | 5 | 8 |
|
|
|
|
这张表要看的不是数字本身，而是状态只依赖前两个位置，所以可以压缩成两个变量。
|
|
|
|
DP 题建议检查这些边界：
|
|
|
|
| 输入 | 重点 |
|
|
| ---------------- | ------------------------ |
|
|
| `n = 0` 或空数组 | 初始化是否覆盖 |
|
|
| 只有 1 个元素 | 是否越界访问 `dp[1]` |
|
|
| 无法组成目标 | 初始值是否能表达“不可达” |
|
|
| 求方案数 | 初始化和遍历顺序是否正确 |
|
|
|
|
常见错误写法：
|
|
|
|
```java
|
|
for (int j = weights[i]; j <= capacity; j++) {
|
|
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // 0-1 背包中是错的
|
|
}
|
|
```
|
|
|
|
0-1 背包中容量要倒序遍历，否则本轮刚更新的状态会被再次使用，相当于同一个物品被选了多次。
|
|
|
|
## 易错点
|
|
|
|
- `dp` 含义不要频繁变化。
|
|
- 初始化不是随便填 0，要看状态含义。
|
|
- 0-1 背包容量倒序，完全背包容量正序。
|
|
- 求方案数和求最值的初始化不同。
|
|
- 子序列题经常需要区分“以 i 结尾”和“前 i 个元素内”。
|
|
|
|
## 高频问题自测
|
|
|
|
- 为什么 DP 的第一步一定是定义状态？
|
|
- 记忆化搜索和递推的区别是什么？什么时候先写记忆化更稳？
|
|
- 0-1 背包为什么容量要倒序遍历？
|
|
- 完全背包为什么容量可以正序遍历？
|
|
- `dp[i]` 表示“以 i 结尾”和表示“前 i 个元素”时，转移有什么区别？
|
|
- 求最少次数、最大价值、方案数时，初始化分别要注意什么？
|
|
|
|
## 推荐练习题
|
|
|
|
- [70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/)
|
|
- [198. 打家劫舍](https://leetcode.cn/problems/house-robber/)
|
|
- [322. 零钱兑换](https://leetcode.cn/problems/coin-change/)
|
|
- [416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/)
|
|
- [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/)
|
|
- [1143. 最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/)
|
|
|
|
<!-- @include: @article-footer.snippet.md -->
|