LeetCodeCampsDay36动态规划part04

01背包，分割等和子集的变式题目

416.分割等和子集是问：能否将背包装满到target值

1049.石头：尽量将背包装满到target值，如果装不到，则最小差值是多少

494.目标和：装满一个到target值，有多少种方法

474.一和零：装满一个背包，最多有多少物品

1049. 最后一块石头的重量 II

https://leetcode.cn/problems/last-stone-weight-ii/

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

1 2	输入：stones = [31,26,33,21,40] 输出：5

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 100

动态规划思路

如何让这一堆石头相撞后，剩下的石头最小？

极端情况下：当把这一堆石头分成两堆并且两堆体积相等时，剩下的石头为零
次优解为：两堆体积尽量相似！剩下的石头最小

这题目之前416.分割等和子集有些像

可以用一个背包装石头，并找一个最小差值：背包的重量 与 剩下石头的重量 差值最小

使用一维背包，dp背包的下标：石头重量，背包dp[i]含义：背包的重量
递推公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])，因为重量就是价值，所以weight[i]=val[i]=stones[i]
dp初始化，一维背包初始化全为零，背包最大容量设置为sumOfStones也是可以的，但将在极端情况下，只要让背包装满sumOfStones的一半就可以了，即令dp的长度为sumOfStones//2
遍历顺序：行遍历对每个石头遍历，列遍历对背包重量（从大到小遍历，范围[sumOfStones // 2, stones[i]]，保证每个物品只添加一次，这样才是01背包；如果从小到大遍历，就会变成完全背包，指每个物品可以放多次）
举例

动态规划代码

时间复杂度：O(m × n) , m是石头总重量（准确的说是总重量的一半），n为石头块数
空间复杂度：O(m)

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sumOfStones = sum(stones)
        target = sumOfStones // 2
        dp = [0] * (target+ 1)
        L = len(stones)
        for i in range(L):
            for j in range(target, stones[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
				
        # # (sumOfStones - dp[target])是一堆，dp[target]是另一堆
        return sumOfStones - dp[target] - dp[target]

494. 目标和

https://leetcode.cn/problems/target-sum/

给你一个非负整数数组 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：

1 2	输入：nums = [1], target = 1 输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

本题思路

本题目需要根据nums求target，看似既要求正数又要求负数情况，但实际上，可以将题目转换成只求正数集，一旦得到了正确的正数集，那sum-正数集就是对应的负数集

令作为正数集的和为targetSum，作为负数集的和（每个数字仍然为正数）为remainSum

则

targetSum + remainSum = sum
targetSum - remainSum = target

targetSum + targetSum - target = sum

targetSum = (sum + target) // 2

现在问题变成了：求有多少种方法装满left，即背包最大容量为left有多少种装法（或有多少种方法装right）

回溯思路

回溯的思路和之前“组合总和”代码相似，但前提也是要把题目转换一个思考方式，不需要真的考虑每次加一个数或减一个数，而是只考虑：

如何获得满足条件的正数集

回溯代码

class Solution:
    def __init__(self):
        self.path = list()
        self.res = 0

    def foo(self, nums, target , currentSum, start):
        if currentSum > target:
            return 

        if currentSum == target:
            self.res += 1
        
        L = len(nums)
        for i in range(start, L):
            self.path.append(nums[i])
            self.foo(nums, target, currentSum + nums[i], i + 1)
            self.path.pop()


    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sumOfnums = sum(nums)
        if sumOfnums < abs(target):
            return 0
        if (sumOfnums + target) % 2:
            return 0
        nums = sorted(nums)
        left = (sumOfnums + target) // 2
        self.foo(nums, left, 0, 0)
        return self.res

动态规划思路

在确定了动态规划里的targetSum值（对应下面代码里的left），则把问题转成了把背包装满到targetSum的问题

dp数组下标与含义：dp[j]下标j表示当前背包容量，有dp[j]个方法把背包装满到target
递推公式：dp[j] = dp[j] + dp[j - nums[i]]

先只考虑物品0，如图：

（这里的所有物品，都是题目中的数字1）。

装满背包容量为0 的方法个数是1，即放0件物品。

装满背包容量为1 的方法个数是1，即放物品0。

装满背包容量为2 的方法个数是0，目前没有办法能装满容量为2的背包。

接下来考虑物品0 和物品1，如图：

装满背包容量为0 的方法个数是1，即放0件物品。

装满背包容量为1 的方法个数是2，即放物品0 或者放物品1。

装满背包容量为2 的方法个数是1，即放物品0 和放物品1。

其他容量都不能装满，所以方法是0。

接下来考虑物品0 、物品1 和物品2 ，如图：

装满背包容量为0 的方法个数是1，即放0件物品。

装满背包容量为1 的方法个数是3，即放物品0 或者放物品1 或者放物品2。

装满背包容量为2 的方法个数是3，即放物品0 和放物品1、放物品0 和物品2、放物品1 和物品2。

装满背包容量为3的方法个数是1，即放物品0 和物品1 和物品2。

dp[2][2] = 3，即放物品0 和放物品1、放物品0 和物品 2、放物品1 和物品2，如图所示，三种方法：

容量为2 的背包，如果不放物品2 有几种方法呢？

有 dp[1][2] 种方法，即背包容量为2，只考虑物品0 和物品1 ，有 dp[1][2] 种方法，如图：

容量为2 的背包，如果放物品2 有几种方法呢？

首先要在背包里先把物品2的容量空出来，装满刨除物品2容量的背包有几种方法呢？

刨除物品2容量后的背包容量为 1。

此时装满背包容量为1 有 dp[1][1] 种方法，即：不放物品2，背包容量为1，只考虑物品 0 和物品 1，有 dp[1][1] 种方法。

如图：

有录友可能疑惑，这里计算的是放满容量为2的背包有几种方法，那物品2去哪了？

在上面图中，你把物品2补上就好，同样是两种方法。

dp[2][2] = 容量为2的背包不放物品2有几种方法 + 容量为2的背包放物品2有几种方法

所以 dp[2][2] = dp[1][2] + dp[1][1] ，如图：

以上过程，抽象化如下：

不放物品i：即背包容量为j，里面不放物品i，装满有dp[i - 1][j]中方法。
放物品i：即：先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[i - 1][j - 物品i容量] 种方法。

本题中，物品i的容量是nums[i]，价值也是nums[i]。

递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

考到这个递推公式，我们应该注意到，j - nums[i] 作为数组下标，如果 j - nums[i] 小于零呢？

说明背包容量装不下 物品i，所以此时装满背包的方法值等于不放物品i的装满背包的方法，即：dp[i][j] = dp[i - 1][j];

所以递推公式：

1 2	if (nums[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

二维DP数组递推公式： dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

去掉维度i 之后，递推公式：dp[j] = dp[j] + dp[j - nums[i]] ，即：dp[j] += dp[j - nums[i]]

这个公式在后面在讲解背包解决排列组合问题的时候还会用到！

以前都是dp[j] = max(dp[j] , dp[j - nums[i]] + xxx)，现在要注意dp的含义是有多少种装包的方法而不是求它的价值

动态规划代码

时间复杂度：O(n × m)，n为正数个数，m为背包容量
空间复杂度：O(m)，m为背包容量

def findTargetSumWays(self, nums: List[int], target: int) -> int:
       sumOfnums = sum(nums)
       if sumOfnums < abs(target):
           return 0
       if (sumOfnums + target) % 2:
           return 0
       nums = sorted(nums)
       left = (sumOfnums + target) // 2
       
       L = len(nums)
       sumOfnums = sum(nums)
       if sumOfnums < abs(target):
           return 0
       if (sumOfnums + target) % 2:
           return 0
       left = (sumOfnums + target) // 2
       
       # dp下标与含义：下标j为背包容量，有dp[j]个方法装满
       dp = [0] * (left + 1)
       # dp初始化，dp[0]初始化为1，装满0的背包有1种方法
       dp[0] = 1
       # 非0下标初始化为0
       for i in range(L):
           for j in range(left, nums[i] - 1, -1):
               # 递推公式dp[j] += dp[j - nums[i]]
               dp[j] += dp[j - nums[i]]
       
       return dp[left]

474. 一和零

https://leetcode.cn/problems/ones-and-zeroes/

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

1
2
3

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

动态规划思路

本题里的物品只有子串，但背包需要使用二维，其中dp[j][k]表示最多有j个0，有k个1的最大子集的大小为dp[j][k]

并且，本题的问题是：装满这个背包，最多可以装多少个物品，最终返回值dp[m][n]

dp数组下标与含义：dp[j][k]表示最多有j个0，有k个1的最大子集的大小为dp[j][k]
递推公式：与前面的公式不同，对于每个物品strs[i]，比如’11001’，需要先判断它有x个0，有y个1；
1. 然后判断dp[j - x][k - y] + 1 与 dp[j][k]的大小，表示如果，如果装得下，则把这个子串’11001’添加进来则会多一个物品
初始化，将dp全部初始化为0
遍历顺序：先遍历物品，但需要对物品计算每个子串的0&1个数；再遍历背包，按0和1进行两层循环的遍历（因为先遍历0或1都可以，不影响）
1. 注意，遍历背包里，仍然需要像回滚dp数组一样，倒序遍历，因为虽然这里的dp是二维数组，但它只是两个维度的容量

动态规划代码

时间复杂度: O(kmn)，k 为strs的长度
空间复杂度: O(mn)

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 使用一个二维dp背包，dp[j][k]表示最多有j个0,k个1的最大子集的大小为dp[j][k]
        # 问，装满这个容器，最多有多少个物品
        # 最终返回dp[m][n]
        # 递推公式(回滚背包)
        # dp[j] = max(dp[j], dp[j - weight[i]] + val[i])
        # 二维dp数组
        # dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1) ，这里的x,y表示某个子串有x个0，y个1，加1表示把这个子串（物品）添加进来
        # dp初始化
        # dp[0][0]=0, 非零下标也初始化为0
        L = len(strs)
        dp = [[0] * (n+1) for _ in range(m+1)]
        # 遍历物品
        for i in range(L):
            # 计算strs[i]的0和1个数
            x0 = 0
            y1 = 0
            for c in strs[i]:
                if c == '0':
                    x0 += 1
                else:
                    y1 += 1
            # 遍历背包容量，分别遍历0和1，顺序可以颠倒
            for j in range(m, x0 - 1, -1):
                for k in range(n, y1 - 1, -1):
                    dp[j][k] = max(dp[j][k], dp[j - x0][k - y1] + 1)
        return dp[m][n]