【代码随想录day36】【C++复健】1049. 最后一块石头的重量 II ； 494. 目标和 ；474.一和零

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

纠结了一下是要定义bagsize为sum/2还是sum/2+1，但在最后return的时候发现，如果设置成sum/2+1的话，没办法保证2*dp[bagsize]和sum之间哪个更大，所以选择了向下取整。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size();int sum = 0;for(int i=0; i<stones.size(); i++){sum += stones[i];}int bagsize = sum/2;vector<int> dp(bagsize+1);for(int i=0; i<n; i++){for(int j=bagsize; j>=stones[i]; j--){dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);}}return sum - 2*dp[bagsize];}
};

494. 目标和

没被递推公式难住，但是却被初始化难住了，因为在我看来，dp[0]是0是1好像都能说得通，但是只有当dp[0]等于1的时候才能引导出正确的后续结果，那就按1来吧。

除此之外还忽略了对于特殊情况的处理逻辑，一个是目标小于sum的情况不行，还有就是当target+sum为奇数，这个时候无法用整数的bagsize算出来这个target+sum，此时也是无解的。但我没加这个处理条件，所以导致了错误的结果。

导致这问题的主要原因还是没搞清楚底下的for循环能处理什么，不能处理什么。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;int n = nums.size();for(int i=0; i<n; i++){sum += nums[i];}if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagsize = (sum + target)/2;vector<int> dp(bagsize+1);dp[0] = 1;for(int i=0; i<n; i++){for(int j=bagsize; j>=nums[i]; j--){dp[j] += dp[j-nums[i]];}}return dp[bagsize];}
};

dp[j][k] = dp[j-count[i][0]][k-count[i][1]] + 1;

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len = strs.size();vector<vector<int>> count(len, vector<int>(2));for(int i=0; i<strs.size(); i++){for(int j = 0; j< strs[i].size(); j++){if(strs[i][j] == '0'){count[i][0] += 1;}else if(strs[i][j] == '1'){count[i][1] += 1;}}}vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i=0; i<count.size(); i++){for(int j=m; j>=count[i][0]; j--){for(int k=n; k>=count[i][1]; k--){dp[j][k] = max(dp[j][k], dp[j-count[i][0]][k-count[i][1]] + 1);}}}return dp[m][n];}
};