目标和-494

[sl1673495]

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号  +  和  -。对于数组中的任意一个整数，你都可以从  +  或  -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。

提示：

• 数组非空，且长度不会超过 20 。
• 初始的数组的和不会超过 1000 。
• 保证返回的最终结果能被 32 位整数存下。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/target-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题的 DP 思路相对难找一点：

横坐标

首先需要确认的一点是，给定的 nums 数组的全部数字的和：

• 最小值 min 是全部选择负数形态的情况。
• 最大值 max 是全部选择正数形态的情况。

那么我们的这我们就遍历这两个值的区间，s = min ~ max 作为 DP 二维数组的横坐标。

纵坐标

纵坐标就按照背包问题的思路，从 n = 0 ~ nums.length 分别考虑选择n 个数字的情况下能去凑成横坐标的解的个数。

状态转移方程

每个数字 num 能够选择整数或负数，以 s = 2 这个坐标为例，假如我们之前已经规划过 [1, 1]，现在到了 [1, 1, 1] 的情况，当前拿到了一个新的数字 1 去凑 2：

• 选用正数的情况下就变成了用之前选择的几个数字去凑 2 - 1。
• 选用负数的情况下就变成了用之前选择的几个数字去凑 2 - (-1) 也就是 2 + 1。

所以状态转移方程是：

dp[n][s] = dp[n - 1][s - num] + dp[n- 1][s + num]

/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
let findTargetSumWays = function (nums, S) {
  let ns = nums.length
  if (!ns) {
    return 0
  }
  let min = nums.reduce((sum, cur) => sum - cur, 0)
  let max = nums.reduce((sum, cur) => sum + cur, 0)

  let dp = []
  for (let n = 0; n < ns; n++) {
    dp[n] = []
  }

  // 基础状态
  for (let s = min; s <= max; s++) {
    let num = nums[0]
    let pickPositive = s === num ? 1 : 0
    // 选负数形态
    let pickNegative = -s === num ? 1 : 0
    dp[0][s] = pickPositive + pickNegative
  }

  for (let n = 1; n < ns; n++) {
    for (let s = min; s <= max; s++) {
      let num = nums[n]
      // 选正数形态
      let pickPositive = dp[n - 1][s - num] || 0
      // 选负数形态
      let pickNegative = dp[n - 1][s + num] || 0
      dp[n][s] = pickNegative + pickPositive
    }
  }
  return dp[ns - 1][S] || 0
}