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];}
};