【LeetCode 】494. 目标和（0-1背包）逐行注释详解

1. 题目描述

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

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

一共有5种方法让最终目标和为3。

注意:

数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。

2. 解题思路（转化成 0-1 背包问题）

假设所有元素的和为sum，所有添加正号的元素和为A，添加负号的元素和为B。则
sum = A + B,
S = A - B,
解方程得 A = (sum + S) / 2。

题意转化成：从数组中选取一些元素使得其和恰好为 (sum + S) / 2。即“恰好装满”的 0 - 1背包问题。求总方案数，将原始状态转移方程中的 max 改成求和。

因为【选与不选这两种方式都是合法的方式，所以加起来是总的方式数。】需要注意的是：虽然这里是恰好装满，但是 dp 的初始值不应该是 -inf。

因为这里求的不是总价值而是方案数，应该全部初始化为 0（除了 dp[0] 应该初始化为 1。)

dp[ i ][ j ] 表示容量为 j 的背包，在区间 [ 0 , i ] 中的物品“选”或者“不选”的情况下最多有多少种方案。

dp[0][0] = 1 表示：背包容量为0，要使得总和为0，那就什么都不选，刚好有这一种方案。

2.1 二维 dp

【注意】：这里的 i 在索引的时候是从 0 开始索引，也就是从 nums[0] 开始索引，与常见的 0 - 1 背包问题有所不同（一般 i 是从 1 开始索引）

Python

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        """ 【二维 dp 0-1背包问题】 dp[i][j]表示容量为j的背包，在区间[0,i]中的物品“选”或者“不选”的情况下最多有多少种方案 """
        n = len(nums)
        Sum = sum(nums)
        if (Sum < S) or (Sum < -S) or (Sum + S) % 2 == 1:   # 目标数比总和还大排除, 奇数，排除
            return 0
        A = (Sum + S) // 2            # 如果不是整除 // 会变成 float 后面不能用于表示列表列数

        dp = [[0] * (A+1) for _ in range(n+1)]
        dp[0][0] = 1       # 背包容量为0，什么都不选的时候总和为0，刚好有这一种方案
        for i in range(1, n+1):
            
            for j in range(0,A+1):
                if nums[i-1] <= j:    # 【注意！！！】 这里的 num 从 nums[0] 开始索引
                    
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
                    
                else:
                    dp[i][j] = dp[i-1][j]   # 选与不选这两种方式都是合法的方式，所以加起来是总的方式数。
        #print(dp)
        return dp[-1][-1]

2.2 一维 dp

【注意】：这里的 i 在索引的时候是从 0 开始索引，也就是从 nums[0] 开始索引，与常见的 0 - 1 背包问题有所不同（一般 i 是从 1 开始索引）

Python

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        """ 【一维 dp 0-1背包问题】 包容量为0，要使得总和为0，那就什么都不选，刚好有这一种方案 参考 https://leetcode-cn.com/problems/target-sum/solution/python-dfs-xiang-jie-by-jimmy00745/ """
        n = len(nums)
        Sum = sum(nums)
        if (Sum < S) or (Sum < -S) or (Sum + S) % 2 == 1:   # 目标数比总和还大排除
            return 0
        A = (Sum + S) // 2            # 如果不是整除 // 会变成 float 后面不能用于表示列表列数

        dp = [0] * (A+1) 
        dp[0] = 1       # 背包容量为0，什么都不选的时候总和为0，刚好有这一种方案
        for i in range(0, n): # 【注意！！！】 此处 nums 是从 0 开始索引
            
            for j in range(A, nums[i]-1, -1):
                # if j >= nums[i]:
                    # 选与不选这两种方式都是合法的方式，所以加起来是总的方式数。
                    dp[j] = dp[j] + dp[j-nums[i]]   # 
     
        #print(dp)
        return dp[-1]

参考

https://www.zhihu.com/search?type=content&q=leetCode中背包问题
https://leetcode-cn.com/problems/target-sum/solution/python-dfs-xiang-jie-by-jimmy00745/
https://leetcode-cn.com/problems/target-sum/solution/python-dfs-xiang-jie-by-jimmy00745/