第一章：动态规划和回溯算法到底谁是谁爹？

labuladong动态规划和回溯算法到底谁是谁爹？

494. 目标和

方法1：动态规划（dp二维数组）

dp[i][j]表示 数组中前i个元素组成和为j的方案数

1. base case:

• 首先初始化数组第0行。如果第一个元素为0，则dp[0][total]=2
  • （-0 和+0 都为0，所以先初始化为2） 比如 [0,1,2], 目标和为3，则有-0+1+2=3，+0+1+2=3
• 否则和为±nums[0] 的位置的方案数置为1

        if nums[0]==0:
            dp[0][total]=2
            # 相当于
            # dp[0][total-nums[0]]=2   # 如何凑出target 和如何把target见=减到0 是一样的
            # dp[0][total+nums[0]]=2
            # 只是此时nums[0]=0，因此写成 dp[0][total]=2
        else:
            dp[0][total-nums[0]]=1  
            dp[0][total+nums[0]]=1

（或者直接用下面的代码来包含nums[0]为0 和非0的情况）

        dp[0][total-nums[0]]=+1
        dp[0][total+nums[0]]=+1

2. 状态转移方程
   保证数组的列索引在0到total*2+1范围内

                l=j-nums[i] if j-nums[i]>=0 else 0
                r=j+nums[i] if j+nums[i]<total*2+1 else 0
                dp[i][j]=dp[i-1][l]+dp[i-1][r]

3. dp[i][j]的含义 : 数组中前i个元素组成和为j的方案数。因为和最大为sum（nums），所以和的范围为 -sum（nums）到 0到 sum（nums）。 数组大小设为[[0 for _ in range(sum(nums)*2+1)] for _ in range(len(nums))]

class Solution(object):
    def findTargetSumWays(self, nums, S):
        total=sum(nums)
        if abs(total)<abs(S):return 0 #若目标和大于数组和，凑不成，返回0
        dp=[[0 for _ in range(total*2+1)] for _ in range(len(nums))]
        #初始化数组第0行
        if nums[0]==0:
            dp[0][total]=2
        else:
            dp[0][total-nums[0]]=1
            dp[0][total+nums[0]]=1

        for i in range(1,len(nums)):
            for j in range(total*2+1):
                # l和r要保证在合法的索引范围内
                l=j-nums[i] if j-nums[i]>=0 else 0
                r=j+nums[i] if j+nums[i]<total*2+1 else 0
                dp[i][j]=dp[i-1][l]+dp[i-1][r]
        return dp[-1][total+S]

方法2：动态规划（0-1背包的变体）

• dp数组行和列都分别增加1，第0列表示背包容量为0，第0行表示（虚拟）物品重量为0（这样做，方便初始化dp数组以及后续dp状态转移）
• 由于加了虚拟的0行和0列， 物品i从 1 开始，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]

以[1,1,2,3]为例，目标和为 target=3.

一种可行的方式为 +1+1-2+3=3 。正数列表为P=[1,1,3] , 负数列表为N=[2] 。 则有
sum（P）- sum（N）=target （1）
另一方面，
sum（P）+sum（N）=sum（nums） （2）
公式（1）与（2）相加，得 sum（P）= （sum（nums）+target）/2
问题转化为 -> 各个物品大小为 [1,1,2,3], 背包容量为（sum（nums）+target）/2，求把背包正好装满的方案数

但是，这里有个与0-1背包的区别：

• 对于0-1 背包，物品大小为正数，可以先对二维数组初始化第0行（除[0][0]位置外全为0）和第0列（全为1）。然后i和j都从1开始遍历
• 对于该问题，列表中可能存在为 0 的元素，因此选不选这个0，都能将容量为0的背包装满。所以只有dp[0][0]=1 （因为是增加的虚拟0行和0列）, 剩下的第0列的其他位置的值用状态转移方程确定 （而不能初始化为1） 。即i从1开始遍历，j从0开始遍历
  • 如 列表为 [0,0,0] , 目标值为 0，则最终的dp数组为[[1], [2], [4], [8]]
  • 如 列表为 [0,0,1]，目标值为 1，则最终的dp数组为[[1, 0], [2, 0], [4, 0], [4, 4]]

class Solution(object):
    def findTargetSumWays(self, nums, S):
        total = sum(nums)
        if abs(total) < abs(S): return 0# 目标和太大
        if (total + S) % 2 != 0: return 0 #(total + S)必须为偶数，即，能被2整除

        volume = (total + S) / 2
        dp = [[0 for _ in range(volume + 1)] for _ in range(len(nums) + 1)]
        dp[0][0]=1

        for i in range(1, len(nums) + 1):
            for j in range( volume + 1):
                if j<nums[i-1]: # 背包太小，装不下
                    dp[i][j]=dp[i-1][j]
                else: # 装和不装的总和
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]
        print(dp)
        return dp[-1][-1]