494. 目标和

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/target-sum/
Star
给你一个整数数组 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
通过次数129,168提交次数258,820

法1 动态规划 二维

思路
将数组nums 分为两份，为 a 和 b，则有：
  • sum(a) + sum(b) = sum(nums)
  • sum(a) - sum(b) = target
所以，sum(a) = (sum(nums) + target) // 2。到此，即相当于寻找一个子集和为 (sum(nums) + target) // 2 的子集个数。
状态定义：dp[i][j] 前i个num可以组成和为j的组合数为多少
状态转移：dp[i][j] = dp[i][j] + dp[i-1][j-num]
初始化：dp[0][0] = 1
题解
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sum_ = sum(nums)
        if abs(target) > abs(sum_):
            return 0
        if (target + sum_) % 2 == 1:
            return 0
        target = (target + sum_) // 2

        dp = [[0]*(target+1) for _ in range(len(nums)+1)]
        
        # 初始化
        dp[0][0] = 1

        for i in range(1, len(nums)+1):
            for j in range(0, target+1):
                dp[i][j] = dp[i-1][j]
                if j - nums[i-1] >= 0:
                    dp[i][j] += dp[i-1][j-nums[i-1]]

        return dp[-1][target]

法2 动态规划 一维

思路
将数组nums 分为两份，为 a 和 b，则有：
  • sum(a) + sum(b) = sum(nums)
  • sum(a) - sum(b) = target
所以，sum(a) = (sum(nums) + target) // 2。到此，即相当于寻找一个子集和为 (sum(nums) + target) // 2 的子集个数。
组合问题，
dp[i] :组成和为i的组合有 dp[i]种，所以最后返回dp[-1]即可
递推公式，遍历 nums，dp[j] 可以由 组成 j-num 的组合数（即dp[j-num]）加当前组合数（dp[j]）
如果 j - num == 0 ，那么应该是 dp[j] + 1。表示，在当前组合数的基础上由于num的出现又多了一种组合数，所以可以直接初始化 dp[0] = 1
题解
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if (target + sum(nums)) % 2 == 1:
            return 0
        if sum(nums) < target:
            return 0
        target = (target + sum(nums)) // 2
        dp = [0 for _ in range(target + 1)]
        dp[0] = 1
        for num in nums:
            for j in range(target, num-1, -1):
                dp[j] = dp[j-num] + dp[j]
        return dp[-1]