目錄

Leecode?1049.最后一塊石頭的重量II

?Leecode?494.目標和

?Leecode?474.一和零

---

Leecode?1049.最后一塊石頭的重量II

題目地址：力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術成長平臺

題目類型：01背包

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 背包的最大容量應當是 sum / 2 ，因為當兩堆石頭的重量最接近的時候mint sum = accumulate(stones.begin(), stones.end(), 0);int target = sum / 2;vector<int> dp(target + 1);for (int i = 0; i < stones.size(); ++i) {for (int j = target; j >= stones[i]; --j) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] * 2;}
};

?

?

?Leecode?494.目標和

題目地址：力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術成長平臺

題目類型：01背包

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// sum = right + left// target = right - left// sum - target = 2left    int sum = accumulate(nums.begin(), nums.end(), 0);if ((sum - target) % 2 == 1 || abs(target) > sum) return 0; // left代表較少那一部分組合的和int left = (sum - target) / 2;// dp數(shù)組的含義是，當求和為i時，組合的數(shù)目vector<int> dp(left + 1);dp[0] = 1;for (int i = 0; i < nums.size(); ++i) {for (int j = left; j >= nums[i]; --j) {dp[j] += dp[j - nums[i]];}}return dp[left];}
};

?Leecode?474.一和零

題目地址：???????力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術成長平臺

題目類型：01背包

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// 存儲個數(shù)vector<pair<int, int>> nums;for (auto &it : strs) {int zero = 0, one = 0;for (auto &c : it) {if (c == '0') zero++;else one++;}nums.push_back({zero, one});}// dp[i][j]代表當有i個0，j個1時，最大的子集長度vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 先物品，后背包for (int k = 0; k < nums.size(); ++k) {// 二維for (int i = m; i >= nums[k].first; --i) {for (int j = n; j >= nums[k].second; --j) {// 注意，這里如果將第k個子集放進來，則代表增加一個子集，value是1，所以直接加1就行了dp[i][j] = max(dp[i][j], dp[i - nums[k].first][j - nums[k].second] + 1);}}}return dp[m][n];}
};

可以少一個循環(huán)，時間復雜度再降一下：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// dp[i][j]含義：當0的容量為i，1的容量為j時，子集的最大數(shù)目// 可知此時最大值問題，故考慮狀態(tài)轉(zhuǎn)移方程1vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int k = 0; k < strs.size(); ++k) {     // 遍歷所有物品，即遍歷所有子集int num0 = 0, num1 = 0;for (char c : strs[k]) {if (c == '0') num0++;else num1++;}for (int i = m; i >= num0; --i) {for (int j = n; j >= num1; --j) {dp[i][j] = max(dp[i][j], dp[i - num0][j - num1] + 1);}}}return dp[m][n];}
};