---
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 -->