题目

题目来源：力扣（LeetCode）

给你一个整数数组 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

思路分析

动态规划

记数组的元素和为 sum，添加 - 号的元素之和为 neg，则其余添加 + 号的元素之和为 sum−neg，得到的表达式的结果为：
(sum - neg) - neg = sum - 2*neg = target
即：
neg = (sum - target) / 2

由于数组 nums 中的元素都是非负整数，neg 也必须是非负整数所以上式成立的前提是 sum - target 为非负偶数。若不符合该条件可直接返回 0 。

若上式成立，为题转化成在数组 nums 中选取若干元素，使得这些元素之和等于 neg，计算选取元素的方案数。我们可以使用动态规划的方法求解。

1、状态定义
定义二维数组 dp，其中 dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数。

2、确定递推公式
当 1 ≤ i ≤ n 时，对于数组 nums 中的第 i 个元素num (i 的计数从 1 开始)，遍历 0≤ j ≤ neg ，计算 dp[i][j] 的值：

  • 如果 j < num，则当前第 i 个元素num 不能选，因此有 dp[i][j] = dp[i - 1][j]

  • 如果 j ≥ num，那么当前第 i 个元素可选，也可不选：

    • 如果选择，则方案数是 dp[i - 1][j - num]
    • 如果不选择，则方案数是 dp[i - 1][j]

因此有 dp[i][j]=dp[i - 1][j] + dp[i - 1][j - num]

因此状态转移方程为：

dp[i][j] = dp[i - 1][j] (j < num)

dp[i][j]=dp[i - 1][j] + dp[i - 1][j - num] (j ≥ num)

在算法实现时我们只考虑 j ≥ num 的情况，因此最终的状态转移方程为：
dp[i][j]=dp[i - 1][j] + dp[i - 1][j - num]

3、状态初始化
当没有任何元素可以选取时，元素和只能是 0，对应的方案数是 1，即起始条件为 dp[0][0] = 1；如果元素和 大于等于 1 时，dp[0][j] 初始化为 0。

4、遍历顺序
01背包问题外层for循环遍历物品，内层for循环遍历背包容量，
那么本题也是，物品就是nums里的数字，背包容量就是题目描述中的添加 - 号的元素之和为 neg

5、输出值
我们输出的是最后一个状态，假设数组nums的长度为 n，则最终答案为dp[n][neg] 。

代码实现

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var findTargetSumWays = function (nums, target) {
  7.   let sum = 0;
  8.   // 计算数组的元素和
  9.   for (const num of nums) {
  10.     sum += num;
  11.   }
  13.   const diff = sum - target;
  14.   if (diff < 0 || diff % 2 !== 0) {
  15.     return 0;
  16.   }
  17.   const n = nums.length, neg = diff / 2;
  18.   const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0));
  19.   // dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数
  20.   dp[0][0] = 1;
  21.   for (let i = 1; i <= n; i++) {
  22.     const num = nums[i - 1];
  23.     for (let j = 0; j <= neg; j++) {
  24.       dp[i][j] = dp[i - 1][j];
  25.       if (j >= num) {
  26.         dp[i][j] += dp[i - 1][j - num];
  27.       }
  28.     }
  29.   }
  30.   return dp[n][neg];
  31. };

空间优化

由于dp 的每一行的计算只和上一行有关，因此可以使用滚动数组的方式，去掉 dp 的第一个维度，将空间复杂度优化到 O(neg)。

实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是 dp[i−1][] 中的元素值。

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var findTargetSumWays = function (nums, target) {
  7.   let sum = 0;
  8.   for (const num of nums) {
  9.     sum += num;
  10.   }
  11.   const diff = sum - target;
  12.   if (diff < 0 || diff % 2 !== 0) {
  13.     return 0;
  14.   }
  15.   const neg = Math.floor(diff / 2);
  16.   const dp = new Array(neg + 1).fill(0);
  17.   dp[0] = 1;
  18.   for (const num of nums) {
  19.     for (let j = neg; j >= num; j--) {
  20.       dp[j] += dp[j - num];
  21.     }
  22.   }
  23.   return dp[neg];
  24. };

参考阅读 https://leetcode-cn.com/problems/target-sum/solution/mu-biao-he-by-leetcode-solution-o0cp/ https://leetcode-cn.com/problems/target-sum/solution/dai-ma-sui-xiang-lu-494-mu-biao-he-01bei-rte9/ https://leetcode-cn.com/problems/target-sum/solution/gong-shui-san-xie-yi-ti-si-jie-dfs-ji-yi-et5b/