题目1:1049. 最后一块石头的重量 II - 力扣(LeetCode)
这道题主要的思路是把题目转换成分成两份,然后转换成一个重量为 sum / 2 的背包去装石头,尽可能将背包装的最大,那么最后最小省的石头就是 (sum - dp[j]) - dp[j] 前边是剩下的石头,后边是能装的最大的石头
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for(int i = 0;i < stones.size();i++) {sum += stones[i];}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]);// std::cout << dp[j] << std::endl;}// std::cout << "-------" << std::endl;}// std::cout << dp[target] << std::endl;return sum - 2* dp[target];}
};
题目2:494. 目标和 - 力扣(LeetCode)
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int i = 0;i < nums.size();i++) {sum += nums[i];}if((sum - target) % 2 != 0) return 0;if(abs(target) > sum) return 0;int bagweight = (sum - target) / 2;vector<int> dp(bagweight + 1, 0);dp[0] = 1;for(int i = 0;i < nums.size();i++) {for(int j = bagweight;j >= nums[i];j--) {dp[j] += dp[j - nums[i]];}}return dp[bagweight];}
};
题目3:474. 一和零 - 力扣(LeetCode)
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for(string str : strs) {int zernums = 0;int onenums = 0;for(char ch : str) {if(ch == '0') zernums++;else onenums++;}for(int i = m;i >= zernums;i--) {for(int j = n;j >= onenums;j--) {dp[i][j] = max(dp[i][j], dp[i - zernums][j - onenums] + 1);}}}return dp[m][n];}
};