day31-数据结构力扣

1049. 最后一块石头的重量 II题目链接1049. 最后一块石头的重量 II - 力扣LeetCode思路1.dp 含义dp[i][j]前 i 块石头容量 j最大可装重量2.递推公式max(不选选)对于第 i 块石头有两种选择不选或选不选第 i 块石头dp[i][j] dp[i-1][j]选第 i 块石头前提石头重量 ≤ 当前容量 jdp[i][j] dp[i-1][j - stones[i-1]] stones[i-1]3.初始化第一行、第一列全为 0dp[0][j] 00 块石头任何容量都装不了最大重量为 0dp[i][0] 0容量为 0任何石头都装不了最大重量为 04.遍历外层石头内层容量5.推导最后取dp[n][target]计算sum - 2*dp提交class Solution: def lastStoneWeightII(self, stones: List[int]) - int: total sum(stones) target total // 2 n len(stones) # 1. dp[i][j]前i个石头容量j最大重量 dp [[0] * (target 1) for _ in range(n 1)] # 4. 遍历顺序先石头后容量 for i in range(1, n 1): w stones[i - 1] for j in range(1, target 1): if j w: # 装不下只能不选 dp[i][j] dp[i - 1][j] else: # 2. 递推公式选/不选 取最大 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] w) # 结果 return total - 2 * dp[n][target]494. 目标和题目链接494. 目标和 - 力扣LeetCode思路1.dp 含义dp[i][j]前 i 个数和为 j 的表达式数目2.递推公式dp[i][j] 加num 减num对第 i 个数不选dp[i][j] dp[i-1][j]选dp[i][j] dp[i-1][j - nums[i-1]]最终递推公式dp[i][j] dp[i-1][j] dp[i-1][j - nums[i-1]]3.初始化dp[0][0] 1dp[0][0] 10 个数字和为 0 的表达式只有1 种什么都不选其余dp[0][j] 0无法凑出非 0 和4.遍历外层数字内层所有可能和5.推导最后取dp[n][target]即为答案提交class Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: total sum(nums) # 无法构成的情况 if (total target) % 2 ! 0: return 0 if abs(target) total: return 0 x (total target) // 2 n len(nums) # 1. dp[i][j]前i个数和为j的方案数 dp [[0] * (x 1) for _ in range(n 1)] # 3. 初始化 dp[0][0] 1 # 4. 遍历顺序 for i in range(1, n 1): num nums[i-1] for j in range(0, x 1): # 2. 递推公式 dp[i][j] dp[i-1][j] if j num: dp[i][j] dp[i-1][j - num] return dp[n][x]474.一和零题目链接474. 一和零 - 力扣LeetCode思路1.dp 含义dp[i][j] i 个 0、j 个 1 的最大子集长度2.递推公式max(不选, 选1)对每个字符串含 zero 个 0one 个 1不选dp[i][j] 原来的值选dp[i - zero][j - one] 1递推公式dp[i][j] max( dp[i][j], dp[i - zero][j - one] 1 )3.初始化全 0全部初始化为00 个 0、0 个 1 时最多选 0 个字符串没有物品时任何容量都是 04.遍历先字符串再倒序遍历 0、1 数量倒序遍历 01 背包标准做法防止重复选取5.结果dp[m][n]提交class Solution: def findMaxForm(self, strs: List[str], m: int, n: int) - int: # 初始化dpi个0j个1最大子集长度 dp [[0] * (n 1) for _ in range(m 1)] # 遍历每个字符串物品 for s in strs: # 统计当前字符串的0和1数量 zero s.count(0) one s.count(1) # 二维01背包必须倒序遍历 for i in range(m, zero - 1, -1): for j in range(n, one - 1, -1): # 递推公式 dp[i][j] max(dp[i][j], dp[i - zero][j - one] 1) return dp[m][n]