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

稍微数学退一下就可以看出实际上还是把数组分成两个部分,去求两个子集的差值的最小值,和昨天最后一题是一样的。

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        target = sum(stones) // 2
        dp = [0] * (target+1)
        for i in stones:
            for j in range(target, i-1, -1):
                dp[j] = max(dp[j], dp[j-i]+i)
        return sum(stones) - 2 * dp[-1]

494.目标和

题目其实就是选取一部分的子集为正,一部分为负,然后和为target,假设一个子集和为left另一个为right,那么可以表示成left - right = target,又有right = sum_-left,则2*left = sum_+targrt。所以就又变成了选取一个子集满足和为(sum_+target)//2的子集个数。当(sum_+target)为奇数和abs(target)>sum_的时候都不可能实现,返回0。这里dp[i]数组表示的是和为i时的可能路径数,初始dp[0]可以看作是和为0且没有数字可以选择的时候,初始化为1,路径数是dp[i]已经有的路径加上选择数字num时的dp[i-num]的路径数。

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sum_ = sum(nums)
        if (sum_ + target) % 2 != 0 or sum_ < abs(target):
            return 0
        tar = (sum_ + target) // 2
        dp = [0] * (tar + 1)
        dp[0] = 1
        for num in nums:
            for i in range(tar, num-1, -1):
                dp[i] += dp[i-num]
        return dp[-1]

474.一和零

先把每个字母的1和0的个数求出来,然后创建一个(m+1)*(n+1)的dp数组,第一个维度表示0的个数,第二个维度表示1的个数。然后对每个物体进行遍历,再对m和n倒序遍历,寻找dp[i][j]和dp[i-num[0]][j-num[1]]+1中的最大值。这里需要倒序的原因和普通一维dp数组一致,本质上这也是一个滚动的二维dp数组,只要是针对每个物体都在同一个dp数组上更新的话就要倒序遍历防止一个物品重复使用。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        nums = [[0, 0] for _ in strs]
        for i in range(len(strs)):
            for s in strs[i]:
                if s == '0':
                    nums[i][0] += 1
                else:
                    nums[i][1] += 1
        dp = [[0] * (n+1) for _ in range(m+1)]
        for num in nums:
            for i in range(m, num[0]-1, -1):
                for j in range(n, num[1]-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-num[0]][j-num[1]]+1)
        return dp[-1][-1]

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部