代码随想录刷题第四十三天

今天为三道0-1背包问题的变种， 分别有三个小问题

1. 给定一个容量为j的背包，尽可能装下物品，找到能装下物品的最大价值
   • dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
2. 给定一个容量为j的背包，找到有多少种方法能够装满背包
   • dp[i][j] += dp[i-1][j-nums[i]]
   • 将左上角dp[0][0]初始化为1， 从这一种方法开始往上累加
3. 给定一个容量为j的背包，找到背包最后装了多少个物品
   • dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+1)

最后一块石头的重量II (LC 1049)

题目思路：

代码实现：

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        allsum = sum(stones)
        target = allsum//2

        dp = [[0 for _ in range(target+1)] for _ in range(len(stones))]

        if stones[0] <= target:
            for j in range(stones[0], target+1):
                dp[0][j] = stones[0]

        for i in range(1, len(stones)):
            for j in range (1, target+1):
                if stones[i] > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])
        
        return allsum-dp[len(stones)-1][target]*2

目标和 (LC 494)

题目思路：

代码实现：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        allsum =sum(nums)
        if (allsum+target)%2==1:
            return 0
        if allsum < abs(target):
            return 0     
        addtarget = (allsum+target)//2

        dp = [[0 for i in range(addtarget+1)] for _ in range(len(nums))]

        if nums[0]<=addtarget:
            dp[0][nums[0]] = 1 

        if nums[0]!=0:
            dp[0][0] = 1
        else:
            dp[0][0] = 2              
        
        for i in range(1, len(nums)):
            for j in range(addtarget+1):
                dp[i][j] = dp[i - 1][j]  # 不选取当前元素
                if nums[i] <= j:
                    dp[i][j] += dp[i-1][j-nums[i]]

        print(dp)
        
        return dp[len(nums)-1][addtarget]

一和零 (LC 474)

题目思路：

代码实现：

三维dp，会超时

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[[0 for _ in range(n+1)] for _ in range(m+1) ] for _ in range(len(strs))]

        zeros, ones = self.count_zeros(strs[0])
        if zeros<=m and ones<=n:
            for j in range(zeros, m+1):
                for k in range(ones, n+1):
                    dp[0][j][k] = 1           
        
        for i in range(1, len(strs)):
            for j in range(m+1):
                for k in range(n+1):
                    zeros, ones = self.count_zeros(strs[i])
                    dp[i][j][k] = dp[i-1][j][k]  # 不选取当前元素
                    if zeros<=j and ones<=k:
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones]+1)

        print(dp)
        
        return dp[len(strs)-1][m][n]

    def count_zeros(self, input_string):
        count = 0
        for char in input_string:
            if char == '0':
                count += 1
        return count, len(input_string)-count

二维dp

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        
        for i in range(len(strs)):
            for j in range(m, -1, -1):
                for k in range(n, -1, -1):
                    zeros, ones = self.count_zeros(strs[i])
                    dp[j][k] = dp[j][k]  # 不选取当前元素
                    if zeros<=j and ones<=k:
                        dp[j][k] = max(dp[j][k], dp[j-zeros][k-ones]+1)
        
        return dp[m][n]

    def count_zeros(self, input_string):
        count = 0
        for char in input_string:
            if char == '0':
                count += 1
        return count, len(input_string)-count