动态规划难，不是因为代码一定长，而是因为状态定义一旦错了，后面的转移方程、初始化和遍历顺序都会跟着错。
面试里不要一上来就背模板。先问自己两个问题：这个问题能不能拆成子问题？当前答案是否依赖前面已经算过的答案？如果这两个问题都成立，再考虑 DP。
面试考察重点
能说清 dp[i] 或 dp[i][j] 的含义。
dp[i]dp[i][j]能写出状态转移方程。
能处理初始化和遍历顺序。
能判断是否可以压缩空间。
能区分背包、子序列、区间等常见类型。
什么时候考虑动态规划？
DP 不是看到“最值”就套。更靠谱的判断是看两个条件：
问题能不能拆成规模更小的同类问题。
子问题会不会被反复计算。
比如斐波那契数列，f(n) 依赖 f(n - 1) 和 f(n - 2)，而 f(n - 2) 会在递归里被反复计算。把这些中间结果存下来，就是 DP。
f(n)f(n - 1)f(n - 2)f(n - 2)面试里可以先从暴力递归说起，再说明哪里重复计算，最后把递归改成记忆化搜索或表格递推。这个过程比直接背 dp 数组更容易让面试官相信你真的理解。
dpDP 五步法
定义状态：dp[i] 到底表示什么。
dp[i]写转移：当前状态从哪些状态推出来。
做初始化：没有前置状态时答案是什么。
定遍历顺序：先算哪些状态，后算哪些状态。
检查样例：用一个小输入手推数组。
其中最重要的是第 1 步。dp[i] 的含义一旦含糊，后面的代码就会变成试出来的。
dp[i]一个好的状态定义通常满足：
能覆盖题目要问的答案。
能从更小状态推出来。
维度尽量少，但不要为了省空间把含义写乱。
一维 DP 示例
爬楼梯问题：
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;
}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]。
idp[i] = dp[i - 1] + dp[i - 2]这题还可以从递归推出来：
到第 i 阶的最后一步，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。到第 i 阶的最后一步，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。所以 dp[i] 只依赖前两个状态，可以把数组压缩成两个变量。空间压缩的前提是你确认旧状态以后不会再用。
dp[i]0-1 背包模板
每个物品只能选一次：
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];
}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]，等于同一个物品被选了多次。这就变成完全背包了。
dp[j]dp[j - weight]0-1 背包的典型问法不一定直接叫背包，像“能否分成两个和相等的子集”，可以转成：能否从数组里选一些数，使它们的和等于总和的一半。
完全背包模板
每个物品可以选多次：
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];
}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[i] 表示前 i 个位置的最优值70、198
爬楼梯/打家劫舍
dp[i] 表示前 i 个位置的最优值
dp[i]i70、198
背包dp[j] 表示容量为 j 时的最优值或方案数416、518、322
背包
dp[j] 表示容量为 j 时的最优值或方案数
dp[j]j416、518、322
子序列dp[i] 或 dp[i][j] 表示以某位置结尾或两个前缀的答案300、1143
子序列
dp[i] 或 dp[i][j] 表示以某位置结尾或两个前缀的答案
dp[i]dp[i][j]300、1143
回文dp[i][j] 表示区间 [i, j] 是否满足条件或最优值647、516
回文
dp[i][j] 表示区间 [i, j] 是否满足条件或最优值
dp[i][j][i, j]647、516
路径dp[i][j] 表示走到格子 (i, j) 的答案62、64
路径
dp[i][j] 表示走到格子 (i, j) 的答案
dp[i][j](i, j)62、64
记忆化搜索和递推怎么选？
两种写法都在存子问题答案。
写法特点适合场景记忆化搜索从目标状态往下递归，按需计算状态转移复杂、递归更自然递推从小状态往大状态填表遍历顺序清楚、方便压缩空间
写法特点适合场景
写法
特点
适合场景
记忆化搜索从目标状态往下递归，按需计算状态转移复杂、递归更自然
记忆化搜索
从目标状态往下递归，按需计算
状态转移复杂、递归更自然
递推从小状态往大状态填表遍历顺序清楚、方便压缩空间
递推
从小状态往大状态填表
遍历顺序清楚、方便压缩空间
如果一开始想不清遍历顺序，可以先写记忆化搜索。等状态关系清楚后，再改成递推。很多树形 DP、区间 DP，用记忆化搜索更容易写对。
面试手写路径
DP 题不建议直接从代码开始。面试手写时，可以先把下面 4 句话讲清楚：
dp 数组的含义是什么，答案最终落在哪个位置。
dp当前状态依赖哪些旧状态，为什么这些旧状态已经算过。
初始化为什么这样写，尤其是 0、1、无穷大分别代表什么。
01遍历顺序为什么不会提前使用未计算或不该重复使用的状态。
如果这 4 句话说不清，代码大概率是靠记忆写出来的，遇到变体就容易散。
代表题精讲：零钱兑换
- 零钱兑换 是完全背包里很适合面试的一题。题目给定硬币面额和目标金额，问凑成目标金额最少需要多少枚硬币，每种硬币可以使用无限次。
状态定义可以这样说：
dp[j] 表示凑成金额 j 所需的最少硬币数。dp[j] 表示凑成金额 j 所需的最少硬币数。初始化是这题的关键。dp[0] = 0，表示凑成金额 0 不需要硬币；其他金额先设成一个不可能的较大值，表示暂时不可达。
dp[0] = 0代码里用到 Arrays.fill，需要导入 java.util.Arrays。
Arrays.filljava.util.Arraysint 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];
}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[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] 表示以 nums[i] 结尾的 LIS 长度必须选 nums[i]，向前找更小值
最长递增子序列
dp[i] 表示以 nums[i] 结尾的 LIS 长度
dp[i]nums[i]必须选 nums[i]，向前找更小值
nums[i]打家劫舍dp[i] 表示前 i 间房子的最大金额第 i 间偷或不偷
打家劫舍
dp[i] 表示前 i 间房子的最大金额
dp[i]i第 i 间偷或不偷
i最长公共子序列dp[i][j] 表示两个前缀的 LCS 长度比较两个前缀最后一个字符
最长公共子序列
dp[i][j] 表示两个前缀的 LCS 长度
dp[i][j]比较两个前缀最后一个字符
回文子串dp[i][j] 表示区间 [i, j] 是否回文依赖内部区间 [i + 1, j - 1]
回文子串
dp[i][j] 表示区间 [i, j] 是否回文
dp[i][j][i, j]依赖内部区间 [i + 1, j - 1]
[i + 1, j - 1]面试里可以主动说一句：这里的 dp[i] 是“以 i 结尾”，不是“前 i 个元素里的最优值”。这句话能避免很多子序列题写错。
dp[i]过程示意和边界样例
以爬楼梯为例，n = 5 时的状态变化如下：
n = 5idp[i - 2]dp[i - 1]dp[i]312342355358
idp[i - 2]dp[i - 1]dp[i]
i
idp[i - 2]
dp[i - 2]dp[i - 1]
dp[i - 1]dp[i]
dp[i]3123
3
1
2
3
4235
4
2
3
5
5358
5
3
5
8
这张表要看的不是数字本身，而是状态只依赖前两个位置，所以可以压缩成两个变量。
DP 题建议检查这些边界：
输入重点n = 0 或空数组初始化是否覆盖只有 1 个元素是否越界访问 dp[1]无法组成目标初始值是否能表达“不可达”求方案数初始化和遍历顺序是否正确
输入重点
输入
重点
n = 0 或空数组初始化是否覆盖
n = 0 或空数组
n = 0初始化是否覆盖
只有 1 个元素是否越界访问 dp[1]
只有 1 个元素
是否越界访问 dp[1]
dp[1]无法组成目标初始值是否能表达“不可达”
无法组成目标
初始值是否能表达“不可达”
求方案数初始化和遍历顺序是否正确
求方案数
初始化和遍历顺序是否正确
常见错误写法：
for (int j = weights[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // 0-1 背包中是错的
}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 含义不要频繁变化。
dp初始化不是随便填 0，要看状态含义。
0-1 背包容量倒序，完全背包容量正序。
求方案数和求最值的初始化不同。
子序列题经常需要区分“以 i 结尾”和“前 i 个元素内”。
高频问题自测
为什么 DP 的第一步一定是定义状态？
记忆化搜索和递推的区别是什么？什么时候先写记忆化更稳？
0-1 背包为什么容量要倒序遍历？
完全背包为什么容量可以正序遍历？
dp[i] 表示“以 i 结尾”和表示“前 i 个元素”时，转移有什么区别？
dp[i]求最少次数、最大价值、方案数时，初始化分别要注意什么？
推荐练习题
- 爬楼梯
- 打家劫舍
- 零钱兑换
- 分割等和子集
- 最长递增子序列
- 最长公共子序列
写在最后
如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。
JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。
如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。