域名交易中心,欧美seo查询,中英文网站用同域名,商城网站建设与维护方案今天做的头皮发麻#xff0c;除了第一道题是自己AC的#xff0c;剩下两道题目都是看视频才AC的#xff0c;主要是看了视频也花了很久时间才想清楚。
1049. 最后一块石头的重量 II
这道题一开始没什么思路#xff0c;但是看到提示说和昨天的分割子集很像#xff0c;然后我…今天做的头皮发麻除了第一道题是自己AC的剩下两道题目都是看视频才AC的主要是看了视频也花了很久时间才想清楚。
1049. 最后一块石头的重量 II
这道题一开始没什么思路但是看到提示说和昨天的分割子集很像然后我就把思路想出来了。这道题目也是先将数组内元素求和然后除以二背包的最大容量就设置为sum / 2。和昨天那道题一样的思路在动态规划的时候让背包尽可能装满就行了。在遍历结束以后求剩下元素与背包最大价值之间的差值即可。
class Solution {
public:int lastStoneWeightII(vectorint stones) {//1.确定dp[i][j]的含义在背包容量为j,下标为[0, i]的数字组合中的最优方案的最大价值//2.确定递推公式 dp[i][j] max(dp[j], dp[j - weight[i]] value[i])//3.dp数组初始化 dp初始化为0向量//4.确定遍历顺序先物品再背包(可互换)//5.打印数组(省略)int sum accumulate(stones.begin(), stones.end(), 0);vectorvectorint dp(stones.size(), vectorint(sum / 2 1));//初始化for(int i 0; i stones.size(); i)dp[i][0] 0;for(int i 1; i sum / 2; i){if(i stones[0]) dp[0][i] stones[0];else dp[0][i] 0;}//开始动态规划for(int i 1; i stones.size(); i){for(int j 1; j sum / 2; j){if(j stones[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - stones[i]] stones[i]);}}return sum - 2 * dp[stones.size() - 1][sum / 2];}
};494. 目标和
笑死思路根本就想不到看了视频才AC的但是按照视频的思路还是遇到一个测试样例(nums [0,0,0,0,0,0,0,0,1],target1)通过不了想了一下把遍历条件中的改成了然后就全部AC了我觉得这个改动主要还是为了应对这个极端的测试案例其余情况下用是可以直接AC的。我发现但凡dp数组元素代表的不是最大价值如符合条件的组合个数符合条件的集合长度等则遍历背包的时候必须要倒序遍历来避免重复问题这道题目主要就难在dp数组的含义很难构造且初始化条件很不好想一旦明确了dp数组的含义和初始条件递推公式起始很好想。
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {//1.确定dp[j]的含义在背包容量为j的情况下,有dp[j]种方法达到指定价值//2.确定递推公式 dp[j] dp[j] dp[my_target - j]//3.dp数组初始化 dp[0] 1//4.确定遍历顺序先物品再背包(背包倒序遍历)//5.打印数组(省略)int sum accumulate(nums.begin(), nums.end(), 0);if(((sum target) % 2 1) || (abs(target) sum)) return 0; //target取值不合理达不到//可以达到targetint m nums.size();int n (sum target) / 2;vectorint dp(n 1, 0);//初始化dp[0] 1;//开始动态规划for(int i 0; i m; i){for(int j n; j 0; j--){if(j nums[i]) continue;dp[j] dp[j - nums[i]];} }return dp.back();}
};474.一和零
被这道题爆杀了刚看到这道题用二维dp数组也不知道该怎么写这道题的背包容量实际上有两个维度一个是0的容量一个是1的容量题目要求的是符合条件的最大子集长度并不是直接求最大价值所以这道题也需要倒序遍历背包dp数组的含义是背包最多能装i个0和j个1的情况下符合条件的子集的最大长度。这道题的初始化很简单dp[0][0] 0。递推公式有点难想如果背包能装下则装下当前字符串后的子集长度为dp[i - x][j - y] 1当然在遍历的时候需要维护最大长度所以应该用max函数将其与自身比较。在遍历结束后直接返回dp[m][n]即可。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {//1.确定dp[i][j]的含义在背包容量最多装i个0和j个1的情况下的最长子集的长度//2.确定递推公式 dp[i][j] max(dp[i - x][j - y] 1, dp[i][j])//其中x为当前遍历元素的0的个数y为当前遍历元素的1的个数//3.dp数组初始化 dp[0] 1//4.确定遍历顺序先物品再背包(背包倒序遍历)//5.打印数组(省略)vectorvectorint dp(m 1, vectorint (n 1, 0));//初始化dp[0][0] 0;//开始动态规划for(string s : strs){ //外层循环遍历字符串物品//统计当前字符串的01个数int x 0, y 0;for(char c : s){if(c 0) x 1;else y 1;}//遍历背包特殊情况用两层for循环才能实现for(int i m; i 0; i--){if(i x) break;for(int j n; j 0; j--){if(j y) break;dp[i][j] max(dp[i - x][j - y] 1, dp[i][j]);}}}return dp[m][n];}
};做的破大防啊
