Question

剑指 Offer II 102. 加减的目标值

题目描述

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

 

注意：本题与主站 494 题相同： https://leetcode.cn/problems/target-sum/

解法

方法一

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    if target < -1000 or target > 1000:
      return 0
    n = len(nums)
    dp = [[0] * 2001 for i in range(n)]
    dp[0][nums[0] + 1000] += 1
    dp[0][-nums[0] + 1000] += 1
    for i in range(1, n):
      for j in range(-1000, 1001):
        if dp[i - 1][j + 1000] > 0:
          dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
          dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
    return dp[n - 1][target + 1000]

class Solution {
  public int findTargetSumWays(int[] nums, int target) {
    if (target < -1000 || target > 1000) {
      return 0;
    }

    int n = nums.length;
    int[][] dp = new int[n][2001];

    dp[0][nums[0] + 1000] += 1;
    dp[0][-nums[0] + 1000] += 1;

    for (int i = 1; i < n; i++) {
      for (int j = -1000; j <= 1000; j++) {
        if (dp[i - 1][j + 1000] > 0) {
          dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000];
          dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000];
        }
      }
    }
    return dp[n - 1][target + 1000];
  }
}

class Solution {
public:
  int findTargetSumWays(vector<int>& nums, int target) {
    int s = 0;
    for (int x : nums) s += x;
    if (s - target < 0 || (s - target) % 2 != 0) return 0;
    target = (s - target) / 2 + 1;
    vector<int> dp(target);
    dp[0] = 1;
    for (int i = 1; i < nums.size() + 1; ++i) {
      for (int j = target - 1; j >= nums[i - 1]; --j) {
        dp[j] += dp[j - nums[i - 1]];
      }
    }
    return dp[target - 1];
  }
};

func findTargetSumWays(nums []int, target int) int {
  if target < -1000 || target > 1000 {
    return 0
  }
  n := len(nums)
  dp := make([][]int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([]int, 2001)
  }
  dp[0][nums[0]+1000] += 1
  dp[0][-nums[0]+1000] += 1
  for i := 1; i < n; i++ {
    for j := -1000; j <= 1000; j++ {
      if dp[i-1][j+1000] > 0 {
        dp[i][j+nums[i]+1000] += dp[i-1][j+1000]
        dp[i][j-nums[i]+1000] += dp[i-1][j+1000]
      }
    }
  }
  return dp[n-1][target+1000]
}

方法二

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    s = sum(nums)
    if s - target < 0 or (s - target) % 2 != 0:
      return 0
    target = (s - target) // 2 + 1
    n = len(nums) + 1
    dp = [[0] * target for _ in range(n)]
    dp[0][0] = 1
    for i in range(1, n):
      for j in range(target):
        dp[i][j] = dp[i - 1][j]
        if nums[i - 1] <= j:
          dp[i][j] += dp[i - 1][j - nums[i - 1]]
    return dp[-1][-1]

class Solution {
  public int findTargetSumWays(int[] nums, int target) {
    int s = 0;
    for (int x : nums) {
      s += x;
    }
    if (s - target < 0 || (s - target) % 2 != 0) {
      return 0;
    }
    target = (s - target) / 2 + 1;
    int[] dp = new int[target];
    dp[0] = 1;
    for (int i = 1; i < nums.length + 1; ++i) {
      for (int j = target - 1; j >= nums[i - 1]; --j) {
        dp[j] += dp[j - nums[i - 1]];
      }
    }
    return dp[target - 1];
  }
}

func findTargetSumWays(nums []int, target int) int {
  s := 0
  for _, x := range nums {
    s += x
  }
  if s-target < 0 || (s-target)%2 != 0 {
    return 0
  }
  target = (s-target)/2 + 1
  dp := make([]int, target)
  dp[0] = 1
  for i := 1; i < len(nums)+1; i++ {
    for j := target - 1; j >= nums[i-1]; j-- {
      dp[j] += dp[j-nums[i-1]]
    }
  }
  return dp[target-1]
}

方法三

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    s = sum(nums)
    if s - target < 0 or (s - target) % 2 != 0:
      return 0
    target = (s - target) // 2 + 1
    n = len(nums) + 1
    dp = [0] * target
    dp[0] = 1
    for i in range(1, n):
      for j in range(target - 1, nums[i - 1] - 1, -1):
        dp[j] += dp[j - nums[i - 1]]
    return dp[-1]

方法四

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    @cache
    def dfs(i, t):
      if i == n:
        if t == target:
          return 1
        return 0
      return dfs(i + 1, t + nums[i]) + dfs(i + 1, t - nums[i])

    ans, n = 0, len(nums)
    return dfs(0, 0)