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

本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
视频讲解：https://www.bilibili.com/video/BV14M411C7oV
https://programmercarl.com/1049.最后一块石头的重量II.html
有一堆石头，每块石头的重量都是正整数。

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

如果 x == y，那么两块石头都会被完全粉碎；

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

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

思考

石头分为两堆，每一堆的总量尽量接近sum/2。求容量为sum/2的背包最大能装的target，则最终剩余为sum - 2*target
dp[i]表示 容量为i的背包能不能装满

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sum_ = sum(stones)
        bags = sum_//2
        #dp[i] 容量为i的背包能不能装满
        dp = [False] * (bags+1)
        dp[0] = True
        for stone in stones:
            for i in range(bags,0,-1):
                if i >= stone:
                    dp[i] = dp[i] or dp[i-stone]
        for i in range(bags,-1,-1):
            if dp[i]:
                res = sum_ - 2 *i
                return res

494. 目标和

大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。
视频讲解：https://www.bilibili.com/video/BV1o8411j73x
https://programmercarl.com/0494.目标和.html
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

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

思考

01背包问题求组合个数，注意递推公式和一些不满足的情况提前返回。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if (sum(nums) + target)%2 !=0:
            return 0 
        new_target = (sum(nums) + target)//2
        if new_target < 0 :
            return 0 
        # dp[i] 容量i的背包装满有几种方案
        dp = [0] * (new_target+1)
        dp[0] = 1
        for num in nums:
            for i in range(new_target,-1,-1):
                if i>=num:
                    dp[i] = dp[i]+dp[i-num]
        return dp[new_target]

474.一和零

通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ
https://programmercarl.com/0474.一和零.html

给你一个二进制字符串数组 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 。

思考

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # dp[i][j] 容量为i个0和j个1的背包可装的最大子集个数
        dp = [[0] * (n+1) for _ in range(m+1)]
        dp[0][0] = 0
        def cal_01(s):
            nums = [0,0]
            for c in s:
                nums[int(c)]+=1
            return nums[0],nums[1]
        for str_ in strs:
            for i in range(m,-1,-1):
                for j in range(n,-1,-1):
                    zeronum,onenum = cal_01(str_)
                    if i>=zeronum and j>=onenum:
                        dp[i][j] = max(dp[i][j],dp[i-zeronum][j-onenum]+1)
        return dp[m][n]