代码随想录算法训练营Day36

发布于:2025-05-01 ⋅ 阅读:(19) ⋅ 点赞:(0)

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

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

题目链接:力扣1049.最后一块石头的重量Ⅱ
在这里插入图片描述

视频链接:代码随想录

1、思路

  • 把这个问题转换成尽可能将 stones 分成两个等分子集,这就和前两道题很相似了!
  • 时间复杂度: O ( m ∗ n ) O(m * n) O(mn)

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 ∗ m ∗ n ) O(k*m*n) O(kmn)

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]


网站公告

今日签到

点亮在社区的每一天
去签到