代码随想录算法训练营第四十三天

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]*(target+1) for _ in range(len(stones))]# 初始化for j in range(target+1):if stones[0] <= j:dp[0][j] = stones[0]for i in range(1,len(stones)):for j in range(1,(target+1)):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]*(target+1)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-t+nums[i]或者j-t-nums[i]的就可以达到j-t，也就是说在如果在dp下标范围内，dp[i][j]的次数就是j-t+nums[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*t+1) for _ in range(len(nums))]for j in range(2*t+1):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*t+1):#print(j-target-nums[i],j-target+nums[i])if j-t-nums[i] >= -t and j-t+nums[i] <= t:#print(1)dp[i][j] += dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]] elif j-t-nums[i] < -t and j-t+nums[i] <= t:#print(2)dp[i][j] += dp[i-1][j+nums[i]] elif j-t-nums[i] >= -t and j-t+nums[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]*(m+1) for _ in range(n+1)]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]