[数据结构与算法]【动态规划】LeetCode 题解：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

题目链接：

https://leetcode.cn/problems/target-sum

题解

其实是 0-1 背包问题，只是做了一些变形。原来的背包问题，是决策物品放入还是不放入，所以可达状态一定是正整数。

到了这题，可达状态就可能变成负数了。所以我们原来背包问题使用的状态转移表，也就是二维数组就要做一些处理了。

为了处理负数的状态值问题，我们可以加一个偏移值，将负数修复为正数。还有一种方式是用哈希表，这样就能用负数了，但缺点是哈希表的读写效率比不上数组。哈希表的解法这里不讲。

本质是求解问题为 0-1背包的计数问题，即求所有路径的总数是多少。

它的状态转移方式为：

dp[i][j] = dp[i-1][j] + dp[i-1][j-weight[i]];

模版是决策物品是否放入，由两种情况汇集，不放入的 dp[i-1][j] 和 dp[i-1][j-weight[i]] 相加。

然后本题要调整为减去或加上 nums[i]，变成：

dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]];

实现时，你还要稍微注意一下索引值越界的处理。

代码实现：

function findTargetSumWays(nums: number[], target: number): number {
  // 初始化 dp 二维数组
  const n = nums.length;
  const sum = nums.reduce((sum, curr) => sum + curr, 0);
  // 全部加起来都小于 target，说明没有运行结果能得到 target
  // 直接返回 0
  if (sum < Math.abs(target)) return 0;

  // sum 就是偏移值，我们加一个 sum 来抵消负数
  // +1 是补上达到 sum 的情况
  const w = sum * 2 + 1;
  const dp: number[][] = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(w).fill(0);
  }

  // 初始化第一阶段的状态
  dp[0][sum - nums[0]] += 1;
  dp[0][sum + nums[0]] += 1;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < w; j++) {
      // 状态转移方程：
      // dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];
      if (j - nums[i] >= 0 && j - nums[i] < w) {
        dp[i][j] += dp[i - 1][j - nums[i]];
      }
      if (j + nums[i] >= 0 && j + nums[i] < w) {
        dp[i][j] += dp[i - 1][j + nums[i]];
      }
    }
  }
  // 这里注意加上偏移值
  return dp[n - 1][sum + target];
};

结尾

本题为 求0-1背包问题的计数解，对应的状态转移方程为：

dp[i][j] = dp[i-1][j] + dp[i-1][j-weight[i]];

这个你得记住，然后在上面魔改就好了。全是套路。

我是前端西瓜哥，欢迎关注我。