【代码随想录训练营】【Day 45】【动态规划-5】| Leetcode 1049, 494, 474-题目

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

  • 代码随想录思路:尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了
  • 为什么两两单个相撞可以等效于两个group相撞:先分成两个数值相近的group,每个group里的元素分别相撞,就等效于两组group都同时减去一个小的值,这样分别减下去就会把较小的元素都消掉,每个group就只剩一个元素了,这样不就“归”成了两个group相撞了吗? 结论:持续进行两两单个相撞【最终】会导致两两group相撞
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        target = sum(stones) // 2
        # dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。
        dp = [0] * (target+1)

        for i in range(len(stones)):
            for j in range(target, stones[i]-1, -1):
                dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])
        
        return abs(dp[target] - (sum(stones)- dp[target]))

494. 目标和

  • 注意 提前终止条件 以及 dp_target 的推导
    • left - right = target,left - (sum-left) = target
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp_target = (sum(nums) + target) // 2
        # dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法
        # 因为从 dp[0] 开始累加,所以初始值应为1
        if (sum(nums) + target) % 2 or abs(target) > sum(nums):
            return 0
        dp = [0] * (dp_target + 1)
        dp[0] = 1

        for num in nums:
            for i in range(dp_target, num-1, -1):
                dp[i] += dp[i - num]
                
        return dp[dp_target]

474. 一和零

  • 代码随想录思路:dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        for num in strs:
            zero_num, one_num = 0, 0
            for c in num:
                if c == "0":
                    zero_num += 1
                else:
                    one_num += 1
            
            for i in range(m, zero_num-1, -1):
                for j in range(n, one_num-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-zero_num][j-one_num]+1)
            
        return dp[m][n]         
上一篇:亚马逊 AWS 视频转码功能、AWS Elemental MediaConvert 中创建和管理转码作业


下一篇:2024-6-10-Model-Agnostic Meta-Learning (MAML)