做策划有帮助的网站,做网站对程序员说那些需求,盘丝洞app破解无限盘币,页面模板图片大小Day30 OK#xff0c;今日份的打卡#xff01;第三十天 以下是今日份的总结最后一块石头的重量 II目标和一和零 以下是今日份的总结
1049 最后一块石头的重量 II 494 目标和 474 一和零
今天的题目难度不低#xff0c;掌握技巧了就会很简单#xff0c;尽量还是写一些简洁代… Day30 OK今日份的打卡第三十天 以下是今日份的总结最后一块石头的重量 II目标和一和零 以下是今日份的总结
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(vectorint stones) {vectorintdp(15001,0);int sum 0;//这堆石头的总重量for(int i 0;istones.size();i) sum stones[i];int target sum / 2;//遍历物品for(int i 0;i stones.size(); i){//遍历背包for(int j target ; jstones[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(vectorint nums, int target) {int sum 0;for(int i 0; i nums.size();i){sum nums[i];}//没有方案if((targetsum)%21||abs(target)sum)return 0;int bagSize (target sum)/2;vectorintdp( bagSize 1,0);dp[0] 1;for(int i 0;inums.size();i){for(int j bagSize;jnums[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个0y个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(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint(n 1, 0)); // 初始化全为0for (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];}写在最后 ----OK今日份的博客就写到这里这一期的动态规划好难想明天继续加油 —还没看下期的题但是我的栈还有一节没写 –追不上时间进度了又欠了三天的笑 -️。
