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

解答

思路：01 背包介绍

01 背包问题：有 $n$ 件物品，其中第 $i$ 个物品的体积为 $v[i]$，价值为 $w[i]$。每件物品 至多选一个，求体积和不超过 $\text{capacity}$ 时的 最大价值和。

回溯三问：

• 当前操作：枚举 第 $i$ 件物品选/不选
• 当前问题：在剩余容量 $c$ 时，从 前 $i$ 个物品中 得到的最大价值和（两个参数）
• 它的子问题：
  • 不选：在剩余容量 $c$ 时，从 前 $i-1$ 个物品中 得到的最大价值和
  • 选：在剩余容量 $c-v[i]$ 时，从前 $i-1$ 个物品中得到的最大价值和 $+w[i]$
  • 两种情况的计算结果，取最大值 返回给它的上一级问题

回溯方程：

$$\text{dfs}(i,c)=max(\text{dfs}(i-1,c),\text{dfs}(i-1,c-v[i])+w[i])$$

代码：01 背包回溯

def zero_one_knapsack(capacity: int, v: List[int], w: List[int]) -> int:
    n = len(v)

    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        
        if c < v[i]:
            return dfs(i - 1, c)
        
        return max(dfs(i - 1, c), dfs(i - 1, c - v[i]) + w[i])
    
    return dfs(n - 1, capacity)

思路：记忆化搜索

如何把目标和转化成 01 背包问题：设 nums 中添加 + 的元素个数为 p，那么添加负号的元素个数为 n - p，因此 nums 的元素和为 p - (n - p) = 2p - n == t，于是要求：

$$p=\frac{n+t}{2}$$

也就是从 nums 中恰好选择 (n + t)/2 个数，前面添加 + 的方案数，也就是和为 (n + t)/2 的数。因此首先要求 $n+t$ 是一个 非负偶数。这种恰好选择也是 01 背包的三种常见变形：

• 至多装 capacity，求方案数/最大价值和
• 恰好装 capacity，求方案数/最大/最小价值和
• 至少装 capacity，求方案数/最大价值和

所求的是 方案数，因此回溯方程为：

$$\text{dfs}(i,c)=\text{dfs}(i-1,c)+\text{dfs}(i-1,c-v[i])$$

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c == 0 else 0 # 恰好装了 target
            
            if c < nums[i]:
                return dfs(i - 1, c)
            
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])
        
        return dfs(n - 1, target)

思路：递推

把记忆化搜索改成递推：

$$f[i][c]=f[i-1][c]+f[i-1][c-v[i]]$$

为了避免出现负数下标，把 f[i] 的下标统统右移一位，即现在的 f[n] 是原来的 f[n-1]：

$$f[i+1][c]=f[i][c]+f[i][c-v[i]]$$

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        f = [[0] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 1 # 等价于原来的 f[-1][0]，与记忆化搜索边界一致

        for i, x in enumerate(nums):
            for c in range(target + 1):
                if c < x:
                    f[i + 1][c] = f[i][c]
                else:
                    f[i + 1][c] = f[i][c] + f[i][c - x]
            
        return f[n][target]

思路：空间优化

原先的递推需要用到二维数组，空间复杂度为 $O(nt)$，但我们注意到，$f[i+1][c]$ 只与 $f[i][c]$ 有关，也就是每时每刻只有 两个一维数组 参与运算。因此我们可以分奇偶来做：当我们计算 f[2] 时，此时只需要用到 f[1]，因此我们可以把答案填到 f[0] 当中。

状态转移方程：

$$f[(i+1)\mathrm{\%}2][c]=f[i\mathrm{\%}2][c]+f[i\mathrm{\%}2][c-v[i]]$$

此时空间复杂度为 $O(2t)$。

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        f = [[0] * (target + 1) for _ in range(2)]
        f[0][0] = 1 # 等价于原来的 f[-1][0]，与记忆化搜索边界一致

        for i, x in enumerate(nums):
            for c in range(target + 1):
                if c < x:
                    f[(i + 1) % 2][c] = f[i % 2][c]
                else:
                    f[(i + 1) % 2][c] = f[i % 2][c] + f[i % 2][c - x]
            
        return f[n % 2][target]

思路：滚动数组优化

那么能不能只用一个数组？也就是去掉第一维，由于递推数组中，f[i+1][c] 是由它正上方的 f[i][c] 和上一行左边的 f[i][c-v[i]] 转移过来的，因此去掉第一维后，如果从左往右递推，那么上一行左边的 f[i][c-v[i]] 就会被 f[i+1][c-v[i]] 提前覆盖掉，因此我们需要 从右往左递推。

$$f[i+1][c]=f[i][c]+f[i][c-v[i]]\Rightarrow f[c]=f[c]+f[c-w[i]]$$

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        f = [0] * (target + 1)
        f[0] = 1 # 等价于原来的 f[-1][0]，与记忆化搜索边界一致

        for x in nums:
            for c in range(target, x - 1, -1):
                f[c] = f[c] + f[c - x]
                
        return f[target]

思路：其他变形

如果把 == target 改为 至多为 target，就是 01 背包问题将最大价值和改为方案数。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 # 至多为 target 情况，容积不够的情况后面判断了
            
            if c < nums[i]:
                return dfs(i - 1, c)
            
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])
                
        return dfs(n - 1, target)

递推写法：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        f = [1] * (target + 1) # f[-1][0]..f[-1][t + 1] 均为 1，对应 i < 0 边界

        for x in nums:
            for c in range(target, x - 1, -1):
                f[c] = f[c] + f[c - x]
                
        return f[target]

如果把 == target 改为 至少为 target。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c <= 0 else 0
            
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])
                
        return dfs(n - 1, target)

递推写法：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)

        if target < 0 or target % 2:
            return 0
        
        target //= 2

        f = [0] * (target + 1)
        f[0] = 1 # 等价于原来的 f[-1][0]，与记忆化搜索边界一致

        for x in nums:
            for c in range(target, - 1, -1):
                f[c] = f[c] + f[max(c - x, 0)]
                
        return f[target]