代码随想录算法训练营Day36

力扣1049.最后一块石头的重量Ⅱ【medium】
力扣474.一和零【meidum】

一、力扣1049.最后一块石头的重量Ⅱ【medium】

题目链接：力扣1049.最后一块石头的重量Ⅱ

视频链接：代码随想录

1、思路

• 把这个问题转换成尽可能将 stones 分成两个等分子集，这就和前两道题很相似了！
• 时间复杂度：$O(m\ast n)$

2、代码

记忆化搜索

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s = sum(stones)
        m = s // 2
        @cache
        def dfs(i:int, c:int) -> int:
            if i < 0:
                return 0
            if c < stones[i]:
                return dfs(i - 1, c)
            return max(dfs(i - 1, c), dfs(i - 1, c - stones[i]) + stones[i])
        max_sum = dfs(len(stones) - 1, m)
        return  s - 2 * max_sum

dp：翻译递推

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s = sum(stones)
        n = len(stones)
        m = s // 2
        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(stones):
            for c in range(m + 1):
                if c < x :
                    f[i + 1][c] = f[i][c]
                else:
                    f[i + 1][c] = max(f[i][c], f[i][c - x] + x)
        return s - 2 * f[n][m]

空间优化：一维数组

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s = sum(stones)
        n = len(stones)
        m = s // 2
        f = [0] * (m + 1)
        for x in stones:
            for c in range(m, x - 1, -1):
                f[c] = max(f[c], f[c - x] + x)
        return s - 2 * f[m]

二、力扣474.一和零【meidum】

题目链接：力扣474.一和零

视频链接：代码随想录

1、思路

• 这道题是0-1背包问题
• 字符串列表里的元素就是物品，并且每个物品的数量为1
• m 和 n 相当于是 2 个背包，这是这道题和之前不一样的地方 ， 之前都是 1 个背包，所以这边只能用2 维的dp数组，因为要表示 2 个背包嘛
• 我们之前处理空间优化——利用滚动数组的时候，一直都是正序遍历物品，再倒序遍历背包，可以避免重复计数
• 时间复杂度：$O(k\ast m\ast n)$

2、代码

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1) ]
        for s in strs:
            zeronum = s.count('0')
            onenum = s.count('1')
            for i in range(m, zeronum - 1, -1):
                for j in range(n, onenum - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i -zeronum][j - onenum] + 1)
        return dp[m][n]