【代码随想录_Day30】1049. 最后一块石头的重量 II 494. 目标和 474.一和零_业界新闻

发布时间:2024-07-18 00:20

阅读量:3

Day30 OK，今日份的打卡！第三十天

以下是今日份的总结

以下是今日份的总结

1049 最后一块石头的重量 II
494 目标和
474 一和零

今天的题目难度不低，掌握技巧了就会很简单，尽量还是写一些简洁代码 ^ _ ^

最后一块石头的重量 II

思路：

1.确定dp数组以及下标的含义
------ dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
2.确定递推公式
------01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
------本题：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
3.dp数组如何初始化
------因为重量都不会是负数，所以dp[j]都初始化为0就可以了
4.确定遍历顺序
------如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
5.举例推导dp数组

值得注意的是

最后dp[target]里是容量为target的背包所能背的最大重量。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

//二维dp数组实现    int lastStoneWeightII(vector<int>& stones) {         vector<int>dp(15001,0);         int sum = 0;         //这堆石头的总重量         for(int i = 0;i<stones.size();i++) sum += stones[i];         int target = sum / 2;         //遍历物品         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];     }

目标和

思路：
既然为target，那么就一定有
left - right = target
left + right = sum
left = (target + sum)/2 。
此时问题就转化为，装满容量为left的背包，有几种方法。

1.确定dp数组以及下标的含义
------ 填满j（包括j）这么大容积的包，有dp[j]种方法
_
2.确定递推公式
------dp[j] += dp[j - nums[i]]，没弄明白什么意思，记住就可以了
_
3.dp数组如何初始化
------在初始化的时候dp[0] 一定要初始化为1
_
4.确定遍历顺序
------nums放在外循环，target在内循环，且内循环倒序
_
5.举例推导dp数组

值得注意的是

dp[j] += dp[j - nums[i]];

   int findTargetSumWays(vector<int>& nums, int target) {         int sum = 0;         for(int i = 0; i < nums.size();i++){             sum += nums[i];         }         //没有方案         if((target+sum)%2==1||abs(target)>sum)return 0;         int bagSize = (target + sum)/2;         vector<int>dp( bagSize + 1,0);         dp[0] = 1;         for(int i = 0;i<nums.size();i++){             for(int j = bagSize;j>=nums[i];j--){                 dp[j] = dp[j] + dp[j-nums[i]];//求组合类问题的公式，都是类似这种             }         }         return dp[bagSize];     }

一和零

思路：
本题中strs 数组里的元素就是物品，每个物品都是一个！
而m 和 n相当于是一个背包，两个维度的背包

1.确定dp数组以及下标的含义
------ dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.确定递推公式
------01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
------本题，strs里的字符串有x个0，y个1。
------所以递推公式：dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
------字符串的x和y相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）
3.dp数组如何初始化
------01背包的dp数组初始化为0就可以。
------因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
4.确定遍历顺序
------一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
5.举例推导dp数组

值得注意的是

这就是一个典型的01背包！只不过物品的重量有了两个维度而已。

    int findMaxForm(vector<string>& strs, int m, int n) {         vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化全为0         for (string str : strs) {             int x = 0, y = 0;             for (char a : str) {                 if (a == '0')//统计当前string的‘0’的个数                     x++;                 if (a == '1')//统计当前string的‘1’的个数                     y++;             }             for (int i = m; i >= x; i--) {                 for (int j = n; j >= y; j--) {                     dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);                 }             }         }          return dp[m][n];     }