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 <= 100

动态规划 中等 每日一题

仍然可以转换为背包问题

题解

输入: 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

sum(P) 前面符号为 + 的集合；sum(N) 前面符号为减号的集合

所以题目可以转化为

sum(P) - sum(N) = target

=> sum(nums) + sum(P) - sum(N) = target + sum(nums)

=> 2sum(P) = target + sum(nums)

=> sum(P) = (target + sum(nums)) / 2

因此题目转化为01背包，也就是能组合成容量为sum(P)的方式有多少种

代码

1. 二维dp

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

2. 一维dp

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sumN = sum(stones)
        n = len(stones)
        neg = sumN//2
        dp = [[0]*(neg+1) for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1,n+1):
            for j in range(neg+1):
                dp[i][j] = dp[i-1][j]
                if j >= stones[i-1]:
                    dp[i][j] = max(dp[i][j],dp[i-1][j-stones[i-1]] + stones[i-1])
        return abs(sumN - dp[n][neg]*2)

3. 一维dp无滚动数组

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sumN = sum(stones)
        n = len(stones)
        neg = sumN//2
        dp = [0]*(neg+1)
        for i in range(1,n+1):
            for j in range(neg,-1,-1):
                # dp[i][j] = dp[i-1][j]
                if j >= stones[i-1]:
                    dp[j] = max(dp[j],dp[j-stones[i-1]] + stones[i-1])
        return abs(sumN - dp[neg]*2)