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

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
  1. 状态转移方程
    保证数组的列索引在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]
  2. dp[i][j]的含义 : 数组中前i个元素组成和为j的方案数。因为和最大为sum(nums),所以和的范围为 -sum(nums)0sum(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)然后ij都从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]

   转载规则


《第一章:动态规划和回溯算法到底谁是谁爹?》 M 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
第一章:动态规划设计:最长递增子序列 第一章:动态规划设计:最长递增子序列
labuladong动态规划设计:最长递增子序列 300. 最长上升子序列 dp数组的含义:以nums[i] 结尾的当前最长上升子序列的长度记录在dp[i]中 状态转移方程:nums[i] 与它之前的元素nums[j]进行比较,若大于num
2020-07-29
下一篇 
第零章:经典动态规划:完全背包问题 第零章:经典动态规划:完全背包问题
labuladong经典动态规划:完全背包问题 动态规划之背包汇总 第零章:动态规划解题套路框架第一章:经典动态规划:0-1 背包问题第零章:经典动态规划:子集背包问题第零章:经典动态规划:完全背包问题 0-1背包 完全背包
2020-07-27
  目录