1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II
假设只有两块石头，那么stones[0] - stones[1]就是答案，这两个石头的重量越相近，结果越小；重量相等时，结果为 0 ；
推演为两堆石头 stones1 和 stones2 ，当两堆石头的重量最接近时，答案stones1 - stones2最小；
对于本题；将石头分成两堆；使得这两堆石头的重量趋近于总重量的一半，这里两堆石头抵消的差值就最小了；
如果总重量为sum，结果stones1 - stones2 = sum - stones2 - stones2
0-1背包问题：背包的最大容量为 sum / 2
i 表示前i个石头，j 表示背包最大容量；dp[j]容量为j的背包能装下的石头最大重量；
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (int i = 0; i < stones.size(); i++) {sum += stones[i];}int n = sum / 2 + 1;vector<int> dp(n);for (int i = 1; i <= stones.size(); i++) {for (int j = n - 1; j >= stones[i - 1]; j--) {dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);}}return sum - dp[n - 1] - dp[n - 1];}
};
494. 目标和
494. 目标和
每一个正整数可以取+号，也可以取-号；
在这一堆和为sum数字中，有a个数取取+号，它们的和是sum_a；有b个数取取-号， 它们的和是sum_b；有：
sum_a - sum_b = target;
sum_a + sum_b = sum;
得到sum_b = (sum - target) / 2;，
对比之前的416. 分割等和子集（是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。）
本题更进一步的求出有几种组合方式；
背包的最大容量为 (sum - target) / 2；
i 表示前i个数字，j 表示背包最大容量；dp[j]容量为j的背包被装满的组合方案数；
初始值：当背包容量为 0 时，不选元素，对应方案数为 1
-
当背包容量
j < num时，此时方案数为dp[i - 1][j]； -
当背包容量
j > num时，
2.1. 数字num不放入背包；此时方案数为dp[i - 1][j]；
2.2. 数字num放入背包；此时方案数为dp[i - 1][j -num]；最后， 当背包容量
j > num时，总方案数为：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num]；
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 < 0 || (sum - target) % 2 != 0) {return 0;}int n = (sum - target) / 2;cout << n << endl;vector<int> dp(n + 1);dp[0] = 1; // 背包容量为0，不选元素，对应方案数为 1for (int i = 1; i < nums.size() + 1; i++) {for (int j = n; j >= nums[i - 1]; j--) {dp[j] = dp[j] + dp[j - nums[i - 1]];}}return dp[n];}
};
474.一和零
474.一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集
最多 有 m 个 0 ，背包的容量就是 m；
最多 有 n 个 1 ，背包的容量就是 n；
对于一个物品（字符串），有两个维度需要考虑，既要考虑 0 的个数，也要考虑 1 的个数；
抽象出一个二维背包dp[i][j]，最多有i 个 0 和 j 个 1 的strs的最长子集长度dp[i][j]；
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
所以，dp[i][j] = dp[i - zeroNum][j - oneNum] + 1;
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // 二维背包for(string str : strs) { // 遍历字符串 int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') {zeroNum++;} else {oneNum++;}}for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};
