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

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