遵化建设招标网站,wordpress手机版边侧导航,网站建设全部教程,c2c定义代码随想录算法训练营第四十三天| 1049. 最后一块石头的重量 II#xff0c;494. 目标和#xff0c;474. 一和零 1049. 最后一块石头的重量 II494. 目标和474. 一和零 1049. 最后一块石头的重量 II
题目链接#xff1a;最后一块石头的重量 II 重点#xff1a; 本题其实就是… 代码随想录算法训练营第四十三天| 1049. 最后一块石头的重量 II494. 目标和474. 一和零 1049. 最后一块石头的重量 II494. 目标和474. 一和零 1049. 最后一块石头的重量 II
题目链接最后一块石头的重量 II 重点 本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小 和 416. 分割等和子集比较相似
0-1背包要素
背包体积sum//2物品价值stones[i]物品重量stones[i]物品可以用一次
动态规划要素
dp[i][j] [0,i]任选石头在背包容量为j的前提下可以达到的最大体积。之后的都和经典0-1问题一样
class Solution:def lastStoneWeightII(self, stones: List[int]) - int:# dp[i][j] [0,i]任选石头在背包容量为j的前提下可以达到的最大体积。target sum(stones)//2dp [[0]*(target1) for _ in range(len(stones))]# 初始化for j in range(target1):if stones[0] j:dp[0][j] stones[0]for i in range(1,len(stones)):for j in range(1,(target1)):if stones[i] j: # 放不进去就用i之前的元素dp[i][j] dp[i-1][j]else:dp[i][j] max(dp[i-1][j], dp[i-1][j-stones[i]]stones[i])#print(dp[-1][-1])return abs(2*dp[-1][-1]-sum(stones))一维 dp[j] 在背包容量为j的前提下可以达到的最大体积。
class Solution:def lastStoneWeightII(self, stones: List[int]) - int:# dp[j] 任选石头在背包容量为j的前提下可以达到的最大体积。target sum(stones)//2dp [0]*(target1)for i in range(len(stones)):for j in range(target,0,-1):if stones[i] j:dp[j] max(dp[j],dp[j-stones[i]]stones[i])return abs(2*dp[-1]-sum(stones))494. 目标和
题目链接目标和
dp[i][j] [0,i]任选元素可以达到j-t的不同表达数目由于只能加减范围是-sum(nums)到sum(nums)初始化dp的第一行只有一个元素所以-i或者i等于j代表的和时就加一递推公式每次多加一个元素可以nums[i]或者-nums[i]所有如果之前的元素可以组成j-tnums[i]或者j-t-nums[i]的就可以达到j-t也就是说在如果在dp下标范围内dp[i][j]的次数就是j-tnums[i]的次数加上j-t-nums[i]的次数。 先不降成一维了自己都搞不清
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:# dp[i][j] [0,i]任选元素可以达到j的不同表达数目t sum(nums)if target t or target -t:return 0dp [[0]*(2*t1) for _ in range(len(nums))]for j in range(2*t1):if nums[0] j-t:dp[0][j] 1if -nums[0] j-t:dp[0][j] 1for i in range(1,len(nums)):for j in range(2*t1):#print(j-target-nums[i],j-targetnums[i])if j-t-nums[i] -t and j-tnums[i] t:#print(1)dp[i][j] dp[i-1][j-nums[i]] dp[i-1][jnums[i]] elif j-t-nums[i] -t and j-tnums[i] t:#print(2)dp[i][j] dp[i-1][jnums[i]] elif j-t-nums[i] -t and j-tnums[i] t:#print(3)dp[i][j] dp[i-1][j-nums[i]]return dp[-1][sum(nums)target]474. 一和零
题目链接一和零 这个背包的重量是两维的需要满足0的数量和1的数量。为了不让dp变成三维的试一下之前的一维累加吧。 dp[i][j] 拥有最多i个0和j个1的最长子集长度。
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) - int:# dp[i][j] 最多拥有i个0和j个1的最长子集长度。dp [[0]*(m1) for _ in range(n1)]for i in range(len(strs)):one strs[i].count(1)zero strs[i].count(0)for j in range(n,-1,-1):for k in range(m,-1,-1):if one j and zero k:dp[j][k] max(dp[j][k],dp[j-one][k-zero]1)return dp[-1][-1]
