代码随想录打卡Day36

今天做的头皮发麻，除了第一道题是自己AC的，剩下两道题目都是看视频才AC的，主要是看了视频也花了很久时间才想清楚。

1049. 最后一块石头的重量 II

这道题一开始没什么思路，但是看到提示说和昨天的分割子集很像，然后我就把思路想出来了。这道题目也是先将数组内元素求和然后除以二，背包的最大容量就设置为sum / 2。和昨天那道题一样的思路，在动态规划的时候让背包尽可能装满就行了。在遍历结束以后，求剩下元素与背包最大价值之间的差值即可。

class Solution {
public:int lastStoneWeightII(vector<int>& 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);vector<vector<int>> dp(stones.size(), vector<int>(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],target=1)通过不了，想了一下，把遍历条件中的>改成了>=，然后就全部AC了，我觉得这个改动主要还是为了应对这个极端的测试案例，其余情况下用>是可以直接AC的。我发现但凡dp数组元素代表的不是最大价值，如符合条件的组合个数，符合条件的集合长度等，则遍历背包的时候必须要倒序遍历来避免重复问题，这道题目主要就难在dp数组的含义很难构造，且初始化条件很不好想，一旦明确了dp数组的含义和初始条件，递推公式起始很好想。

class Solution {
public:int findTargetSumWays(vector<int>& 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;vector<int> 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(vector<string>& 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.打印数组(省略)vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));//初始化dp[0][0] = 0;//开始动态规划for(string s : strs){  //外层循环遍历字符串（物品）//统计当前字符串的0，1个数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];}
};

做的破大防啊！！！！！！