LeetCode 494：目标和（动态规划/01背包问题）—— 题解

欢迎阅读欢迎来到「目标和」题解之旅本文将带你深入理解动态规划与背包问题的巧妙结合。在开始之前建议你先了解题目背景这是一道经典的动态规划问题涉及 01 背包的变种。明确学习目标掌握将「目标和」问题转化为背包问题的思路理解二维和一维解法的区别。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行。本文将从问题转化、状态定义、转移方程、初始化、填表顺序到代码实现一步步带你深入理解。如果你对动态规划或背包问题还不熟悉不用担心我们会从最基础的原理讲起。一、题目494. 目标和 - 力扣LeetCode二、做题思路问题转化前置分析 互动思考在继续阅读前尝试自己推导一下这个转化过程。为什么P (sum target) / 2如果(sum target)是奇数会怎样设所有添加号的数之和为P添加-号的数之和为N则P N sum数组总和P - N target目标结果联立解得P (sum target) / 2。因此原问题等价于从数组中选择若干个数使它们的和恰好等于P求方案数。若(sum target)为奇数 或P 0则无解直接返回0。1. 状态表示核心基础本题转化为 01 背包求方案数问题。定义dp[i][j]表示从前i个数中选取若干个数使总和恰好为j的方案总数。i范围0到n0表示一个数都不选j范围0到PP为目标和。该状态能覆盖所有前缀的组合情况便于累计方案数。 互动提问为什么状态定义中i要从 0 开始如果从 1 开始定义dp[i][j]表示前 i 个数i≥1初始化会有什么不同2. 状态转移方程关键难点对于第i个数数值nums[i-1]有两种互斥决策不选方案数为dp[i-1][j]。选前提是j nums[i-1]方案数为dp[i-1][j - nums[i-1]]。3. 初始化边界防护代码中只设置dp[0][0] 1其余元素默认0。为什么这样足够dp[0][0] 1表示从前0个数中选取凑出总和0的方案有且仅有 1 种即空集什么数都不选。dp[0][j] 0j 0没有数可选时无法凑出任何正数方案数为0默认初始化即可。dp[i][0]i 0的自动推导根据状态转移方程当j 0时dp[i][0] dp[i-1][0] (0 nums[i-1] ? ... : 0)。由于nums[i-1] 0j nums[i-1]不成立因此选的情况为0所以dp[i][0] dp[i-1][0]。逐行传递最终dp[i][0]始终等于dp[0][0] 1表示“不选任何数”这一种方案始终有效。这完全符合预期无需额外初始化。4. 填表顺序递推方向dp[i][j]依赖上一行dp[i-1][j]和dp[i-1][j - nums[i-1]]因此需要按行从上到下i从 1 到n列从左到右j从0到P遍历。这样能保证每个状态依赖的上一行值已经计算完成。为什么j必须从0开始遍历状态转移方程中j可以取0表示目标和为0的方案。在递推过程中dp[i][0]的值需要被正确计算。由于nums[i-1] 0j nums[i-1]在j0时不成立因此选的情况不会发生dp[i][0]完全继承dp[i-1][0]从而保持为1即始终存在“什么都不选”这一种方案。若从j1开始遍历则dp[i][0]永远不会被更新其值将停留在初始化时的0而非应有的1这会导致后续所有依赖dp[i-1][0]的转移例如当某个nums[i-1] j时dp[i-1][0]为 0 就会丢失方案。因此为了保持状态的完整性j必须从0开始。5. 返回值目标映射最终返回dp[n][P]即从全部n个数中选出若干个数使总和恰好等于P的方案总数。该值即为原问题中满足运算结果为target的表达式个数。三、代码class Solution { public: int findTargetSumWays(vectorint nums, int target) { // 1. 计算数组总和 int sum 0; for (auto x : nums) { sum x; } // 2. 转化为0/1背包问题 // 设正数部分和为 P负数部分和为 N则 P - N targetP N sum // 解得 P (sum target) / 2。 // 问题变为从 nums 中选出若干个数使其和为 P 的方案数。 int aim (sum target) / 2; // 3. 边界条件若 (sumtarget) 为奇数 或 aim 0则无解 if ((sum target) % 2 ! 0 || aim 0) { return 0; } int n nums.size(); // 4. 创建dp表二维 // dp[i][j] 表示从前 i 个数中选取若干个数使其和恰好为 j 的方案数 vectorvectorint dp(n 1, vectorint(aim 1, 0)); // 5. 初始化 // 前0个数中选出和为0的方案数为1空集即 dp[0][0] 1。 // 为什么只设这一个因为 dp[0][j]j0显然为0无法凑出正数和 // 且后续 dp[i][0]i0会通过状态转移自动计算 // 不选第 i 个数时 dp[i][0] dp[i-1][0] // 由于 j nums[i-1] 不成立nums[i-1] 0所以选的情况不会发生 // 因此 dp[i][0] 始终继承 dp[i-1][0]最终保持为1符合“不选任何数”这一种方案。 dp[0][0] 1; // 6. 填表顺序外层遍历物品i从1到n内层遍历容量j从0到aim // 为什么内层 j 从 0 开始因为每个容量 j 都可能成为目标且状态转移需要 // 访问 dp[i-1][j]不选当前数和 dp[i-1][j-nums[i-1]]选当前数。 // 即使 j0也需要继承上一行 dp[i-1][0] 的值保持“空集”方案数 // 所以必须从 0 开始遍历不能从 1 开始而跳过 0。 for (int i 1; i n; i) { for (int j 0; j aim; j) { // 7. 状态转移方程 // 不选第 i 个数继承 dp[i-1][j] dp[i][j] dp[i - 1][j]; // 选第 i 个数前提j nums[i-1]加上 dp[i-1][j-nums[i-1]] if (j nums[i - 1]) { dp[i][j] dp[i - 1][j - nums[i - 1]]; } } } // 8. 返回值dp[n][aim] 即为所有方案数 return dp[n][aim]; } };四、流程图五、优化1. 状态转移方程关键难点 互动挑战尝试在不看下方代码的情况下自己写出从二维状态转移方程推导到一维形式的过程。为什么一维必须倒序遍历不选方案数保持不变即dp[j]仍为上一轮的值。选前提是j nums[i-1]方案数为上一轮dp[j - nums[i-1]]。因此一维转移为dp[j] dp[j - nums[i-1]]当j nums[i-1]时。2. 填表顺序递推方向外层循环遍历每个物品i从 1 到n内层循环必须逆序遍历容量j从aim到nums[i-1]。为什么要倒序因为dp[j]的更新依赖dp[j - nums[i-1]]这个值必须是上一轮未处理当前物品的状态才能保证每个物品最多被选一次01 背包性质。如果采用正序dp[j - nums[i-1]]可能已经在当前物品的处理中被提前更新导致物品被重复使用结果错误。为什么j只降到nums[i-1]当j nums[i-1]时无法选取当前物品dp[j]保持原值无需更新因此可以缩小遍历范围减少无用计算。class Solution { public: int findTargetSumWays(vectorint nums, int target) { // 求和并计算目标正数和即背包容量——此部分与二维版本相同略过详细推导 int sum 0; for (auto x : nums) sum x; int aim (sum target) / 2; if ((sum target) % 2 ! 0 || aim 0) return 0; int n nums.size(); // 1. 一维滚动数组 dp[j]表示“当前已处理的部分元素”中和为 j 的方案数 // 初始时未处理任何元素只有 dp[0] 1空集其余为0 vectorint dp(aim 1, 0); dp[0] 1; // 2. 外层遍历每个物品相当于二维中的行 for (int i 1; i n; i) { // 3. 内层倒序遍历容量 j // ① 为什么倒序—— 因为 dp[j] 依赖上一轮的 dp[j - nums[i-1]] // 若正序dp[j - nums[i-1]] 可能已被当前物品更新导致重复选取。 // 倒序确保用到的仍是“上一轮”的状态即未考虑当前物品时。 // ② 为什么 j 从 aim 降到 nums[i-1]—— // 当 j nums[i-1] 时无法选取当前物品dp[j] 保持原值无需更新 // 因此只遍历可选的容量区间减少无用计算。 for (int j aim; j nums[i - 1]; j--) { // 4. 状态转移一维形式 // dp[j] 原有值 不选当前物品的方案数继承自上一轮 // 加上 选当前物品的方案数 dp[j - nums[i-1]]也是上一轮的值 // 累加后即得到本轮的方案数 dp[j] dp[j - nums[i - 1]]; } } // 5. 返回容量为 aim 的方案总数 return dp[aim]; } };3. 复杂度分析与对比一维滚动数组解法复杂度分析时间复杂度O(n × aim)其中n为数组长度aim (sum target) / 2。外层循环遍历n个物品i从 1 到n内层循环遍历容量j从aim到nums[i-1]。最坏情况下每个物品的内层循环都要遍历aim次因此总操作次数约为n × aim。与二维解法的时间复杂度相同因为两种解法都进行了双重循环只是内部状态更新的方式不同。空间复杂度O(aim)。一维滚动数组只使用了一个长度为aim 1的dp数组。相比二维解法的O(n × aim)空间一维解法将空间消耗降低了一个数量级尤其当n较大时优势明显。与二维解法的对比维度二维解法一维滚动数组解法对比说明时间复杂度O(n × aim)O(n × aim)两者相同都是双重循环空间复杂度O(n × aim)O(aim)一维解法显著更优节省了O(n)倍空间状态定义dp[i][j]表示前i个数和为j的方案数dp[j]表示当前已处理物品中和为j的方案数一维解法隐去了物品维度通过滚动更新复用数组状态转移dp[i][j] dp[i-1][j] dp[i-1][j-nums[i-1]]dp[j] dp[j - nums[i-1]]倒序一维形式更简洁但必须倒序遍历以保证正确性初始化dp[0][0] 1其余为 0dp[0] 1其余为 0两者本质相同一维只需初始化一维数组遍历顺序外层i正序内层j正序0 → aim外层i正序内层j倒序aim → nums[i-1]一维必须倒序防止同一物品被重复使用适用场景教学、调试、需要保留中间状态生产环境、内存敏感、大规模数据一维解法是空间优化的标准实践总结一维滚动数组解法在时间复杂度不变的前提下将空间复杂度从O(n × aim)优化到O(aim)是 01 背包问题空间优化的经典技巧。其核心在于通过倒序遍历容量来保证每个物品只被使用一次同时复用同一数组记录状态。 闭幕 恭喜你完成了「目标和」问题的学习为了巩固知识并进一步拓展建议你 动手实践在 LeetCode 上提交代码尝试不同的测试用例。 举一反三思考如果数组包含负数或零解法需要如何调整 延伸学习探索其他背包变种问题如「分割等和子集」「零钱兑换」等。你认为哪个问题与「目标和」最相似如果你觉得本文对你有帮助欢迎 点赞/收藏 关注作者 留言讨论祝你刷题愉快早日攻克动态规划