（动态规划+DFS）494. 目标和-开发者社区

题目

给你一个非负整数数组nums和一个整数target。

向数组中的每个整数前添加'+'或'-'，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。

返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

算法

定义两个变量：

数组所有元素总和为S；
最终表达式里，带正号的元素和为 p，带负号的元素和为 q。

得出下面两个公式

所有元素要么带正号、要么带负号，所以p + q = S
题目要求表达式结果等于 target，即p - q = target

可以推导出：

p = ( S + target) / 2
q = ( S - target) / 2

不管是选 p 还是 q，是等价的

p 和 q 是互补关系：只要你选出一个子集的和等于 p，剩下的所有元素自然就组成和为 q 的集合；反过来，选出一个子集和为 q，剩下的自然就是 p。两种选择对应的符号分配方案数完全一一对应，最终算出的结果一模一样，不存在选谁对、选谁错的区别。

为了更快的获取数据，所以需要选更小的值

外层遍历 n 个元素，内层从容量倒序遍历到 0，容量越大，内层循环的总轮次越多，计算开销越高。
既然选 p、选 q 结果完全一样，那肯定选数值更小的那个当容量，让内层循环的范围尽可能小，计算效率最高。

target 正负两种情况，对比 p 和 q 的大小

target ≥ 0
- p = (S + target)/2，q = (S - target)/2
- 显然 q < p（分子里减去了 target，结果更小）
- 这时候更小的容量是 q = (S - target)/2
target < 0：比如 target=-3，代入公式：
- p = (S + target)/2 = (S - |target|)/2
- q = (S - target)/2 = (S + |target|)/2
- 显然 p < q（分子里减去了 | target|，结果更小）
- 这时候更小的容量是 p = (S - |target|)/2
所以，不管 target 是正还是负，两个子集和里更小的那个值，永远等于(S - |target|) / 2

记忆化每次的计算结果：memo[i][c]

只使用 nums[0] 到 nums[i] 这些数字，凑出总和 c，一共有多少种选法。
只考虑nums[0..i]这些数字，凑出总和恰好为 c 的方案数
i 的范围是 0 到 nums.length-1
c 的范围是 0 到 (S - |target|) / 2
初始化这个数组
- -1 表示该状态尚未计算：用 -1 作为特殊标记。因为方案数量不会是负数，所以不会和正常答案冲突。
- 0 表示计算过，但确实没有方案

上面的思想实现方法有两种：

DFS：递归搜索
动态规划：后续可以进行空间优化

动态规划优化：将二维 DP 数组压缩为一维数组，减少空间占用，同时通过倒序遍历，保证每个数字最多使用一次。

二维数组状态转移方程为：f[i+1][c]=f[i][c]+f[i][c-x]
- f[i][c]：不选当前数字，方案数不变
- f[i][c-x]：选择当前数字，之前只需要凑出 (c-x)。
计算第 (i+1) 行时，只依赖第 (i) 行，并不需要更早的行。
使用一维数组实现：f[c] += f[c-x]
- f[c]：目前已经处理的数字中，凑出总和c的方案数。
- f[c] += f[c-x]：保留原有方案，再加入“选择当前数字”的方案。
  - c必须倒序遍历：让f[c-x]保持本轮更新前的值，避免重复使用当前数字。
- 含义是：处理到当前数字时，凑出总和c的方案数。
- 必须倒序遍历：每个数字只能使用一次。
  - 倒序遍历：读取的f[c-x]仍然是处理当前数字之前的旧值，确保当前数字最多使用一次。
  - 正序遍历：读取的f[c-x]可能已经被当前数字更新过，导致同一个数字重复使用。这对应完全背包的转移方式。

代码

递归：记忆化搜索

importjava.util.Arrays;classSolution{publicintfindTargetSumWays(int[]nums,inttarget){// 1. 计算数组中所有数字的总和ints=0;for(intx:nums){s+=x;}// 2. 将问题转换为子集和问题// s 原本是数组总和// 减去 |target|，得到两倍的较小子集之和s-=Math.abs(target);// 如果 s < 0，说明数组总和小于 |target|，// 无论如何添加正负号，都不可能得到 target//// 如果 s 是奇数，那么 s / 2 不是整数，// 不存在满足条件的子集if(s<0||s%2==1){return0;}// 3. 转换成：统计和恰好等于 m 的子集数量intm=s/2;// 背包容量，即目标子集的和intn=nums.length;// memo[i][c] 表示：// 只考虑 nums[0..i] 这些数字，// 凑出总和恰好为 c 的方案数//// i 的范围是 0 到 n-1// c 的范围是 0 到 mint[][]memo=newint[n][m+1];// 初始化记忆化数组// -1 表示该状态尚未计算// 0 表示计算过，但确实没有方案for(int[]row:memo){Arrays.fill(row,-1);}// 4. 从最后一个数字开始搜索// 统计所有和为 m 的子集数量returndfs(n-1,m,nums,memo);}/** * 统计只使用 nums[0..i] 时， * 凑出总和恰好为 c 的方案数 */privateintdfs(inti,intc,int[]nums,int[][]memo){// 递归终止条件：// 所有数字都考虑完了if(i<0){// 剩余容量为 0：// 一个数字都不选，也恰好凑出了目标值// 这种方案有 1 种//// 剩余容量不为 0：// 已经没有数字可以选，因此方案数为 0returnc==0?1:0;}// 如果该状态之前已经计算过，直接返回缓存结果if(memo[i][c]!=-1){returnmemo[i][c];}// 选择一：不选 nums[i]// 目标容量仍然是 c，只考虑前面的数字intres=dfs(i-1,c,nums,memo);// 选择二：选 nums[i]// 只有 nums[i] <= c 时才能选择// 选择后，剩余容量变成 c - nums[i]if(c>=nums[i]){res+=dfs(i-1,c-nums[i],nums,memo);}// 缓存当前状态的结果，避免重复计算returnmemo[i][c]=res;}}

动态规划

classSolution{publicintfindTargetSumWays(int[]nums,inttarget){ints=0;for(intx:nums){s+=x;}s-=Math.abs(target);if(s<0||s%2==1){return0;}intm=s/2;intn=nums.length;int[][]f=newint[n+1][m+1];f[0][0]=1;for(inti=0;i<n;i++){for(intc=0;c<=m;c++){if(c<nums[i]){f[i+1][c]=f[i][c];// 只能不选}else{f[i+1][c]=f[i][c]+f[i][c-nums[i]];// 不选 + 选}}}returnf[n][m];}}

空间优化：1个数组

classSolution{publicintfindTargetSumWays(int[]nums,inttarget){// 第一步：计算所有数字的总和ints=0;for(intx:nums){s+=x;}// 第二步：将目标和问题转换成子集和问题// 转换后的目标子集和为 (sum - |target|) / 2s-=Math.abs(target);// 总和不足以达到目标，或者无法整除 2，都不可能有方案if(s<0||s%2==1){return0;}intm=s/2;// 背包容量int[]f=newint[m+1];// 一个数字都不选，凑出总和 0，只有一种方案f[0]=1;// 依次处理每个数字for(intx:nums){// 倒序遍历，避免当前数字被重复使用for(intc=m;c>=x;c--){// 不选 x：原有的 f[c] 种方案// 选 x：原本凑出 c-x 的方案，每种都可以加上 xf[c]+=f[c-x];}}// 返回凑出目标和 m 的方案数returnf[m];}}