代码随想录算法训练营第42天 [1049. 最后一块石头的重量 II 494. 目标和 474.一和零]
**一、1049. 最后一块石头的重量 II **
链接: 代码随想录.
思路:石头相撞重量最小,最小的情况就是刚好分为两组大小相同的,这样相撞后重量就为0
所以转化为 重量之和的一半 target容量的背包,尽可能装满,石头的重量和价值都是stones[i]
dp[j] 容量为j的背包最大重量为dp[j]
做题状态:看解析后做出来了
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//石头相撞重量最小,最小的情况就是刚好分为两组大小相同的,这样重量就为0//所以转化为 重量之和的一半 target容量的背包,尽可能装满,石头的重量和价值都是stones[i]//dp[j] 容量为j的背包最大重量为dp[j]int sum = 0;for(int n : stones){sum+=n;}int target = sum/2;vector<int> dp(target+1,0);for(int i = 0;i<stones.size();i++){for(int j = target;j>=stones[i];j--){dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum-dp[target]-dp[target];}
};
二、494. 目标和
链接: 代码随想录.
思路:将数组中需要添加+的记为left ,需要添加-的记为right
数组元素中的和为sum,数组元素加了符号后的和为targeet
得到 left+right = sum left-right = target
推导得到 left = (sum+target)/2 如果不能整除,肯定没有解,直接返回0
代入一下示例 left = (5+3)/2 = 4
相当于left的和要凑为4
相当于背包容量为4,从nums中取物品装满背包有多少种方式
dp[j] 表示容量为j的背包,有dp[4]种方式
dp[0] = 1
递推公式 dp[j] += dp[j-nums[i]]
做题状态:看解析后做出来了
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// 将数组中需要添加+的记为left ,需要添加-的记为right// 数组元素中的和为sum,数组元素加了符号后的和为targeet// 得到 left+right = sum left-right = target// 推导得到 left = (sum+target)/2 如果不能整除,肯定没有解,直接返回0// 代入一下示例 left = (5+3)/2 = 4// 相当于left的和要凑为4// 相当于背包容量为4,从nums中取物品装满背包有多少种方式// dp[j] 表示容量为j的背包,有dp[4]种方式// dp[0] = 1// 递推公式 dp[j] += dp[j-nums[i]]int sum = 0;for (int n : nums) {sum += n;}if ((sum + target) % 2 == 1 || abs(target) > sum) {return 0;}int temp = (sum + target) / 2;vector<int> dp(temp + 1);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = temp; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[temp];}
};
三、474.一和零
链接: 代码随想录.
思路:一共有str种物品,要同时满足m个0的背包和n个1的背包
做题状态:看解析后做出来了
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (string str : strs) {int one = 0;int zero = 0;for (char s : str) {if (s == '1') {one++;} else {zero++;}}for (int i = m; i >= zero; i--) {for (int j = n; j >= one; j--) {dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);}}}return dp[m][n];}
};