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

题目

思路与解法

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for(int i=0;i<stones.size();i++){sum += stones[i];}// 问题转换为：//  先求得，背包容量为target时，能得到的最大价值val；//  然后得，sum-target - val，就是最小的可能重量。int target = sum/2;// dp数组含义：//  当背包容量为i时，放入小于等于当前物品序号的物品能够得到的最大价值// 本体中，让背包容量为总和的一半，然后得到最大的价值// 也就是将石头等分，让两部分尽可能相近，最后的差值自然最小vector<int> dp(target+1, 0);// 初始化 dp 数组//  确实好像不太需要，因为一维不会像二维一样去上一行找东西，一维只有一行，只会去前面找东西。for(int i=stones[0];i < dp.size();i++){dp[i] = stones[0];}// 先遍历 物品for(int j=1;j<stones.size();j++){// 后遍历 背包for(int i=target;i>=0;i--){if(i>=stones[j]){dp[i] = max(dp[i], dp[i-stones[j]]+stones[j]);}}}return sum-dp[target] - dp[target];}
};

494. 目标和

题目

思路与解法

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int i=0;i<nums.size();i++) sum += nums[i];int left = (sum+target)/2;if ((sum+target<0)||(sum+target)%2 == 1) return 0;// dp数组含义://  dp[i]，nums中使和为i有dp[i]种方法vector<int> dp(left + 1, 0);// 递推公式： dp[i] = dp[i-nums[j]] + dp[i]// dp数组初始化：//  dp[0] = 1dp[0] = 1;// 先遍历物品for(int i = 0;i<nums.size();i++){// 后遍历背包for(int j = dp.size()-1;j>=nums[i];j--){dp[j] = dp[j-nums[i]] + dp[j];}}return dp[left];}
};

474.一和零

题目

思路与解法

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// dp数组含义：//  dp[m][n]:m个0，n个1时，最大子集长度为dp[m][n]vector<vector<int>> dp(m+1, vector<int>(n+1, 0));// 初始化dp数组dp[0][0] = 0;// 先遍历物品for(int k = 0;k<strs.size();k++){int count0 = std::count(strs[k].begin(), strs[k].end(), '0');int count1 = std::count(strs[k].begin(), strs[k].end(), '1');// 后遍历背包for(int i = m;i>=count0;i--){for(int j = n;j>=count1;j--){dp[i][j] = max(dp[i-count0][j-count1] + 1, dp[i][j]);}}}return dp[m][n];}
};