动态规划面试题总结：状态转移、背包、子序列与 Java 模板

Guide约 2670 字大约 9 分钟

动态规划难，不是因为代码一定长，而是因为状态定义一旦错了，后面的转移方程、初始化和遍历顺序都会跟着错。

面试里不要一上来就背模板。先问自己两个问题：这个问题能不能拆成子问题？当前答案是否依赖前面已经算过的答案？如果这两个问题都成立，再考虑 DP。

面试考察重点

能说清 dp[i] 或 dp[i][j] 的含义。
能写出状态转移方程。
能处理初始化和遍历顺序。
能判断是否可以压缩空间。
能区分背包、子序列、区间等常见类型。

什么时候考虑动态规划？

DP 不是看到“最值”就套。更靠谱的判断是看两个条件：

问题能不能拆成规模更小的同类问题。
子问题会不会被反复计算。

比如斐波那契数列，f(n) 依赖 f(n - 1) 和 f(n - 2)，而 f(n - 2) 会在递归里被反复计算。把这些中间结果存下来，就是 DP。

面试里可以先从暴力递归说起，再说明哪里重复计算，最后把递归改成记忆化搜索或表格递推。这个过程比直接背 dp 数组更容易让面试官相信你真的理解。

DP 五步法

定义状态：dp[i] 到底表示什么。
写转移：当前状态从哪些状态推出来。
做初始化：没有前置状态时答案是什么。
定遍历顺序：先算哪些状态，后算哪些状态。
检查样例：用一个小输入手推数组。

其中最重要的是第 1 步。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;
}

状态含义：到第 i 阶有多少种走法。转移方程：dp[i] = dp[i - 1] + dp[i - 2]。

这题还可以从递归推出来：

到第 i 阶的最后一步，要么从 i-1 走 1 步上来，要么从 i-2 走 2 步上来。

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

容量要倒序遍历，避免同一个物品在一轮里被重复使用。

倒序遍历是 0-1 背包最容易被问的点。假设容量正序遍历，计算 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];
}

容量正序遍历，允许当前物品被重复使用。

完全背包里，正序遍历容量正是为了允许当前物品重复使用。比如零钱兑换，每种硬币可以用多次，计算更大金额时可以基于当前硬币已经参与过的状态继续转移。

如果题目问的是“组合数”还是“排列数”，遍历顺序也会变：

组合数：通常先遍历物品，再遍历容量。
排列数：通常先遍历容量，再遍历物品。

这块面试不一定问很深，但遇到零钱兑换 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 句话讲清楚：

dp 数组的含义是什么，答案最终落在哪个位置。
当前状态依赖哪些旧状态，为什么这些旧状态已经算过。
初始化为什么这样写，尤其是 0、1、无穷大分别代表什么。
遍历顺序为什么不会提前使用未计算或不该重复使用的状态。

如果这 4 句话说不清，代码大概率是靠记忆写出来的，遇到变体就容易散。

代表题精讲：零钱兑换

322. 零钱兑换是完全背包里很适合面试的一题。题目给定硬币面额和目标金额，问凑成目标金额最少需要多少枚硬币，每种硬币可以使用无限次。

状态定义可以这样说：

dp[j] 表示凑成金额 j 所需的最少硬币数。

初始化是这题的关键。dp[0] = 0，表示凑成金额 0 不需要硬币；其他金额先设成一个不可能的较大值，表示暂时不可达。

代码里用到 Arrays.fill，需要导入 java.util.Arrays。

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]`
无法组成目标	初始值是否能表达“不可达”
求方案数	初始化和遍历顺序是否正确

常见错误写法：

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 个元素”时，转移有什么区别？
求最少次数、最大价值、方案数时，初始化分别要注意什么？

写在最后

如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。

JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。

如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。