吉林 网站备案 照相,wordpress社群模板,做视频网站赚钱吗,国外外链平台代码随想录刷题第四十三天
今天为三道0-1背包问题的变种#xff0c; 分别有三个小问题
给定一个容量为j的背包#xff0c;尽可能装下物品#xff0c;找到能装下物品的最大价值 dp[i][j] max(dp[i-1][j], dp[i-1][j-nums[i]]nums[i]) 给定一个容量为j的背包#xff0c;找…代码随想录刷题第四十三天
今天为三道0-1背包问题的变种 分别有三个小问题
给定一个容量为j的背包尽可能装下物品找到能装下物品的最大价值 dp[i][j] max(dp[i-1][j], dp[i-1][j-nums[i]]nums[i]) 给定一个容量为j的背包找到有多少种方法能够装满背包 dp[i][j] dp[i-1][j-nums[i]]将左上角dp[0][0]初始化为1 从这一种方法开始往上累加 给定一个容量为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//2dp [[0 for _ in range(target1)] for _ in range(len(stones))]if stones[0] target:for j in range(stones[0], target1):dp[0][j] stones[0]for i in range(1, len(stones)):for j in range (1, target1):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 (allsumtarget)%21:return 0if allsum abs(target):return 0 addtarget (allsumtarget)//2dp [[0 for i in range(addtarget1)] for _ in range(len(nums))]if nums[0]addtarget:dp[0][nums[0]] 1 if nums[0]!0:dp[0][0] 1else:dp[0][0] 2 for i in range(1, len(nums)):for j in range(addtarget1):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(n1)] for _ in range(m1) ] for _ in range(len(strs))]zeros, ones self.count_zeros(strs[0])if zerosm and onesn:for j in range(zeros, m1):for k in range(ones, n1):dp[0][j][k] 1 for i in range(1, len(strs)):for j in range(m1):for k in range(n1):zeros, ones self.count_zeros(strs[i])dp[i][j][k] dp[i-1][j][k] # 不选取当前元素if zerosj and onesk: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 0for char in input_string:if char 0:count 1return count, len(input_string)-count二维dp
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) - int:dp [[0 for _ in range(n1)] for _ in range(m1)]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 zerosj and onesk:dp[j][k] max(dp[j][k], dp[j-zeros][k-ones]1)return dp[m][n]def count_zeros(self, input_string):count 0for char in input_string:if char 0:count 1return count, len(input_string)-count
