[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

这道题能够大概看出来想要考察我们动态规划的解法。而且看起来，数组中的数字只有两种选取情况，加或者减似乎是要使用背包问题的解法。

但背包问题只有选择与不选择两种情况，因此我们需要对题目进行改造，使其满足 0-1 背包问题的特征。

设所有添加减号的整数和为 negSum，则所有添加加号的整数和为 posSum = sum - negSum。

而若要获取满足题意的表达式的话， 需要满足 posSum - negSum = target。

因此可得 negSum = (sum - target) / 2，且 negSum 一定为非负整数，否则无法由非负整数构造出来。若不为非负整数直接 return。

那么，接下来的问题就转变为：在数组 nums 中，是否选取某个数字加入到 negSum 中，最终使其塞满背包。

这样，题目就被转变为经典的 0-1 背包问题了。

function findTargetSumWays(nums: number[], target: number): number {
  // 每个数字有两个选择，加或者减
  // 设所有添加减号的整数和为 negSum，则所有添加加号的整数和为 sum - negSum
  // 若需要符合题意的话，需要满足 (sum - negSum) - negSum = target
  // 则可得：negSum = (sum - target) / 2，且 negSum 一定为非负整数，否则无法由非负整数构造出来
  const sum = nums.reduce((prev, curr) => prev + curr);
  const negSum = (sum - target) / 2;
  if (negSum < 0 || negSum % 1 !== 0) return 0;

  const len = nums.length;

  // 接下来的问题就转变为：是否选取某个数字加入到 negSum 中，转变为 0-1 背包问题
  const dp = Array(len + 1)
    .fill(0)
    .map(x => Array(negSum + 1).fill(0));
  dp[0][0] = 1;

  for (let i = 1; i <= len; i++) {
    // 由于 i 从 1 计数，取数字索引时减掉 offset
    const num = nums[i - 1];
    for (let j = 0; j <= negSum; j++) {
      dp[i][j] = dp[i - 1][j];
      // 如果当前数字比背包剩余量小，则只能选择不取
      // 若可以选择当前值，表达式数量可以加上，背包剩余量为 j - nums[i-1] 的情况
      if (j >= num) {
        dp[i][j] += dp[i - 1][j - num];
      }
    }
  }
  return dp[len][negSum];
}

当然，这里我们注意到dp[i] 只与 dp[i-1] 有关，且dp[j]的取值在左侧。因此可以进行节省空间复杂度的操作。这里就不再演示，留给大家做思考题了。