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到n（0表示一个数都不选），j范围0到P（P为目标和）。该状态能覆盖所有前缀的组合情况，便于累计方案数。

🤔 互动提问：为什么状态定义中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] = 0（j > 0）：没有数可选时，无法凑出任何正数，方案数为0，默认初始化即可。
dp[i][0]（i > 0）的自动推导：
根据状态转移方程，当j = 0时，dp[i][0] = dp[i-1][0] + (0 >= nums[i-1] ? ... : 0)。由于nums[i-1] > 0，j >= 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] > 0，j >= nums[i-1]在j=0时不成立，因此选的情况不会发生，dp[i][0]完全继承dp[i-1][0]，从而保持为1（即始终存在“什么都不选”这一种方案）。
若从j=1开始遍历，则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(vector<int>& nums, int target) { // 1. 计算数组总和 int sum = 0; for (auto x : nums) { sum += x; } // 2. 转化为0/1背包问题： // 设正数部分和为 P，负数部分和为 N，则 P - N = target，P + N = sum， // 解得 P = (sum + target) / 2。 // 问题变为：从 nums 中选出若干个数，使其和为 P 的方案数。 int aim = (sum + target) / 2; // 3. 边界条件：若 (sum+target) 为奇数 或 aim < 0，则无解 if ((sum + target) % 2 != 0 || aim < 0) { return 0; } int n = nums.size(); // 4. 创建dp表（二维） // dp[i][j] 表示从前 i 个数中选取若干个数，使其和恰好为 j 的方案数 vector<vector<int>> dp(n + 1, vector<int>(aim + 1, 0)); // 5. 初始化： // 前0个数中选出和为0的方案数为1（空集），即 dp[0][0] = 1。 // 为什么只设这一个？因为 dp[0][j]（j>0）显然为0（无法凑出正数和）， // 且后续 dp[i][0]（i>0）会通过状态转移自动计算： // 不选第 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]]（选当前数）。 // 即使 j=0，也需要继承上一行 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(vector<int>& 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 vector<int> 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`，其余为 0	`dp[0] = 1`，其余为 0	两者本质相同，一维只需初始化一维数组
遍历顺序	外层`i`正序，内层`j`正序（0 → aim）	外层`i`正序，内层`j`倒序（aim → nums[i-1]）	一维必须倒序，防止同一物品被重复使用
适用场景	教学、调试、需要保留中间状态	生产环境、内存敏感、大规模数据	一维解法是空间优化的标准实践