【代码随想录训练营】【Day 45】【动态规划-5】| Leetcode 1049, 494, 474
需强化知识点
题目
1049. 最后一块石头的重量 II
- 代码随想录思路：尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了
- 为什么两两单个相撞可以等效于两个group相撞：先分成两个数值相近的group，每个group里的元素分别相撞，就等效于两组group都同时减去一个小的值，这样分别减下去就会把较小的元素都消掉，每个group就只剩一个元素了，这样不就“归”成了两个group相撞了吗？ 结论：持续进行两两单个相撞【最终】会导致两两group相撞
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
target = sum(stones) // 2
# dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
dp = [0] * (target+1)
for i in range(len(stones)):
for j in range(target, stones[i]-1, -1):
dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])
return abs(dp[target] - (sum(stones)- dp[target]))
494. 目标和
- 注意 提前终止条件 以及 dp_target 的推导
- left - right = target，left - (sum-left) = target
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp_target = (sum(nums) + target) // 2
# dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
# 因为从 dp[0] 开始累加，所以初始值应为1
if (sum(nums) + target) % 2 or abs(target) > sum(nums):
return 0
dp = [0] * (dp_target + 1)
dp[0] = 1
for num in nums:
for i in range(dp_target, num-1, -1):
dp[i] += dp[i - num]
return dp[dp_target]
474. 一和零
- 代码随想录思路：dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n+1) for _ in range(m+1)]
for num in strs:
zero_num, one_num = 0, 0
for c in num:
if c == "0":
zero_num += 1
else:
one_num += 1
for i in range(m, zero_num-1, -1):
for j in range(n, one_num-1, -1):
dp[i][j] = max(dp[i][j], dp[i-zero_num][j-one_num]+1)
return dp[m][n]
