代码随想录算法训练营 Day31 | 动态规划 part04

1049. 最后一块石头的重量 II有一堆石头用整数数组stones表示。其中stones[i]表示第i块石头的重量。每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为x和y且x y。那么粉碎的可能结果如下如果x y那么两块石头都会被完全粉碎如果x ! y那么重量为x的石头将会完全粉碎而重量为y的石头新重量为y-x。最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回0。class Solution { public: int lastStoneWeightII(vectorint stones) { // 特判如果只有一块石头直接返回其重量 // 注其实下面的逻辑也能处理这种情况这个判断可以省略但写上更严谨 if(stones.size() 1) return stones[0]; // 1. 计算总重量 int sum 0; for(int i : stones) sum i; // 2. 确定背包容量 // 目标是将石头分成两堆目标是让其中一堆的重量尽可能接近 sum/2 int n sum / 2; // 3. 定义 DP 数组 // dp[j] 表示容量为 j 的背包能装下的最大石头重量 vectorint dp(n 1, 0); // 4. 0-1 背包求解 for(int i 0; i stones.size(); i){ for(int j n; j stones[i]; j--){ dp[j] max(dp[j], dp[j - stones[i]] stones[i]); } } // 5. 推导结果 // dp[n] 是其中一堆石头的重量接近 sum/2 的那一堆 // 另一堆的重量是 sum - dp[n] // 两堆碰撞后剩下的最小重量 (sum - dp[n]) - dp[n] return sum - 2 * dp[n]; } };总结1. 核心思想抵消题目中石头两两碰撞小的粉碎大的减去小的。这其实就是在做 减法。想象一下如果我们把石头分成两堆A堆 和 B堆。A堆的总重是 WAB堆的总重是 WB。如果拿 A 堆的一块石头去撞 B 堆的一块石头本质上就是让 WA 和 WB​ 做减法。为了让最后剩下的石头最小我们需要 让 WA​ 和 WB​ 尽可能接近。最佳情况是 WAWB​sum/2此时结果为 0。所以问题转化成了在容量为 sum/2 的背包里尽可能多装石头。2. 关键公式推导一堆重量dp[n]这是我们算出来的不超过 sum/2 的最大重量。另一堆重量sum - dp[n]。剩余最小重量(sum - dp[n]) - dp[n] sum - 2 * dp[n]。您的代码中最后一句return sum - 2 * dp[n];正是这个数学逻辑的体现。3. 对比总结分割等和子集问能不能正好装满sum/2。判断dp[target] target。最后一块石头的重量 II问装满sum/2后还差多少或者说剩多少。直接返回sum - 2 * dp[target]。494. 目标和给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加或-然后串联起所有整数可以构造一个 表达式 例如nums [2, 1]可以在2之前添加在1之前添加-然后串联起来得到表达式2-1。返回可以通过上述方法构造的、运算结果等于target的不同 表达式 的数目。class Solution { public: int findTargetSumWays(vectorint nums, int target) { int sum 0; for(int i : nums) sum i; // 1. 排除无解情况 // 如果总和都达不到 target 的绝对值或者 (sum target) 是奇数无法整除 2 if (sum abs(target)) return 0; if ((sum target) % 2 1) return 0; // 2. 推导背包容量 // 设加法的总和为 x减法的总和为 sum - x // x - (sum - x) target 2x target sum x (target sum) / 2 // 此时问题转化为从 nums 中选数填满容量为 x 的背包有多少种方法 int n (target sum) / 2; // 3. 定义 DP 数组 // dp[j] 表示填满容量为 j 的背包有 dp[j] 种方法 vectorint dp(n 1, 0); // 4. 初始化 // dp[0] 必须初始化为 1 // 理解填满容量为 0 的背包有一种方法那就是“什么都不装” // 如果 dp[0] 是 0后面的递推将全部归零乘法原理中的 0 dp[0] 1; // 5. 状态转移 for(int i 0; i nums.size(); i){ for(int j n; j nums[i]; j--){ // 递推公式dp[j] dp[j - nums[i]] // 意义当前填满容量 j 的方法数 之前填满 j 的方法数 之前填满 j-nums[i] 的方法数 // (即把当前物品 nums[i] 放入背包看之前有多少种填满剩余空间的方法) dp[j] dp[j - nums[i]]; } } return dp[n]; } };总结1. 数学建模将/-运算转化为子集和问题是解决这道题的突破口。公式推导left - right target,left right sumleft (sum target) / 2。2. 递推公式的变化这是这道题与前面题目最大的不同最值问题分割等和子集、石头重量dp[j] max(dp[j], dp[j-nums[i]] ...)求最大价值。组合问题目标和dp[j] dp[j - nums[i]]求方案数。为什么是想象一下我们要凑成金额j当前硬币面值是nums[i]。如果我们决定使用这枚硬币那么剩下的金额就是j - nums[i]。既然剩下的金额j - nums[i]有dp[j - nums[i]]种凑法那么凑成j的方法数自然就增加了dp[j - nums[i]]种。3. 初始化的陷阱dp[0] 1是必须要初始化的。如果dp[0] 0那么无论怎么递推所有的dp[j]都会保持为 0因为任何数乘以 0 都是 0。可以这样理解凑出总和为 0确实有一种方法什么都不选。474. 一和零给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度该子集中 最多 有m个0和n个1。如果x的所有元素也是y的元素集合x是集合y的 子集 。class Solution { public: int findMaxForm(vectorstring strs, int m, int n) { // 1. 定义 DP 数组 // dp[i][j] 表示最多有 i 个 0 和 j 个 1 的子集的最大长度 // 这是一个“二维背包”两个维度0的容量和1的容量都需要考虑 vectorvectorint dp(m 1, vectorint(n 1, 0)); // 2. 遍历物品字符串数组 for (string s : strs) { // 统计当前字符串中 0 和 1 的数量即物品的“重量” int zeroNum 0, oneNum 0; for (char c : s) { if (c 0) zeroNum; else if (c 1) oneNum; } // 3. 状态转移二维背包的 0-1 背包写法 // 必须从后向前遍历确保每个字符串物品只被使用一次 for (int i m; i zeroNum; i--) { for (int j n; j oneNum; j--) { // 递推公式 // dp[i][j] max(不选当前字符串, 选当前字符串) // 选当前字符串子集长度 1容量相应减少 dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1); } } } return dp[m][n]; } };总结1. 为什么是“二维费用背包”在标准的背包问题中我们只有一个容量限制如重量。而在本题中我们要选出一个子集同时满足0 的个数 ≤m≤m1 的个数 ≤n≤n这就相当于有两个维度的“背包容量”。物品重量(zeroNum, oneNum)物品价值1每选一个字符串子集长度12. 遍历顺序的关键双层逆序循环for (int i m; i zeroNum; i--) for (int j n; j oneNum; j--)因为每个字符串只能选一次。逆序遍历保证了计算dp[i][j]时用到的dp[i-zeroNum][j-oneNum]是 上一轮 的数据即不包含当前字符串的数据。如果是正序遍历就会变成完全背包同一个字符串被选多次虽然这在逻辑上说不通一个字符串不能重复计数但在 DP 数值计算上会导致错误的结果。3. 复杂度分析时间复杂度O(L×m×n)。其中 L 是字符串数组的长度m,n是给定的容量。还需要加上统计 0/1 个数的时间 O(Lengthstr)。空间复杂度O(m×n)。