题目链接：1049. 最后一块石头的重量 II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
x == y，那么两块石头都会被完全粉碎；x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
文章讲解/视频讲解：https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
思路，把这一堆石头分成两堆，两堆石头重量和的差就是最后一块石头的重量。
什么时候最后一块石头的重量最小？当然是两堆石头重量差不多的时候。
计算stones的重量之和sum，我们的目标是设置背包大小为sum / 2的情况下，装下重量尽可能大的石块。
设置一个二维dp数组，其中dp[i][j]表示背包大小为j，遍历了0 ~ i石块的情况下，能够装下的最大重量。dp数组的递推式为: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i])。如何初始化，也就是对第一行赋值？当j >= stones[0]时，将dp[0][j]赋值为stones[0]，否则赋值为0。遍历顺序？由于此时是二维dp，顺序不那么重要，i与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<vector<int>> dp(stones.size(), vector<int>(target + 1, 0));
for(int j = 0;j<=target;j++){
if(j >= stones[0]) dp[0][j] = stones[0];
}
for(int i = 1;i<stones.size();i++){
for(int j = 0;j<=target;j++){
if(j < stones[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
}
}
return sum - dp[stones.size() - 1][target] - dp[stones.size() - 1][target];
}
};
// 滚动数组
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, 0);
for(int j = 0;j<=target;j++){
if(j >= stones[0]) dp[j] = stones[0];
}
for(int i = 1;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 - 2 * dp[target];
}
};
题目链接：494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
文章讲解/视频讲解：https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
我们令数组中添加’+‘的数字绝对值之和为pos_sum，数组中添加’-'的数字绝对值之和为neg_sum。按照题意，我们有pos_sum - neg_sum = target。计算数组nums中所有数字的和为sum，我们又有pos_sum + neg_sum = sum，结合两个式子，我们可以得到pos_sum = (target + sum) / 2。因此，题目中要求解的 通过上述构造、运算结果等于target的不同表达式的数目，等价于数组中和为pos_sum的不同组合的数目。
注意，当(target + sum) % 2 ！= 0，或者abs(target) > sum时，找不出这样的组合。
首先构造一个二维dp数组，dp[i][j]代表了0 ~ i范围内的数字中，组合为j的次数。为了使组合不会重复，我们让i从小到大遍历。初始化时，令dp[0][0] = 1，其他位置等于0，这个是从公式的结果反推过来的。然后再对i = 0时初始化，如果j = nums[0]，则令dp[0][j] += 1。dp数组的递推式为：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]。
// 原写法
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 pos_sum = target + (sum - target) / 2;
vector<vector<int>> dp(nums.size(), vector<int>(pos_sum + 1, 0));
dp[0][0] = 1;
for(int j = 0;j<=pos_sum;j++){
if(j == nums[0]) dp[0][j] += 1;
}
for(int i = 1;i<nums.size();i++){
for(int j = 0;j<=pos_sum;j++){
if(j < nums[i]) dp[i][j] = dp[i - 1][j];
else{
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
}
return dp[nums.size() - 1][pos_sum];
}
};
// 滚动数组
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 pos_sum = target + (sum - target) / 2;
vector<int> dp(pos_sum + 1, 0);
dp[0] = 1;
for(int i = 0;i<nums.size();i++){
for(int j = pos_sum;j>=nums[i];j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[pos_sum];
}
};
题目链接：474.一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
文章讲解/视频讲解：https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
求解strs数组中每一个字符串中0的个数和1的个数，前者存入zeros数组，后者存入ones数组。
对于这道题，需要开一个三维的dp数组，dp[i][j][k]代表了在0 ~ i下标的字符串中，限制最多有j个0，k个1，能够获得的最大子集长度。
如何初始化？当i等于0时，从0到m遍历j，从0到n遍历k，当j >= zeros[0] && k >= ones[0]时，dp[0][j][k] = 1。
递推公式为：
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - zeros[i]][k - ones[i]] + 1);
遍历顺序为，三层循环，i、j、k均为从小到大遍历。
// 原写法
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<int> zeros(strs.size(), 0);
vector<int> ones(strs.size(), 0);
for(int i = 0;i<strs.size();i++){
int zeroCount = 0, oneCount = 0;
for(int j = 0;j<strs[i].size();j++){
if(strs[i][j] == '0') zeroCount++;
if(strs[i][j] == '1') oneCount++;
}
zeros[i] = zeroCount;
ones[i] = oneCount;
}
vector<vector<vector<int>>> dp(zeros.size(), vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
for(int j = 0;j<=m;j++){
for(int k = 0;k<=n;k++){
if(j >= zeros[0] && k >= ones[0]) dp[0][j][k] = 1;
}
}
for(int i = 1;i<zeros.size();i++){
for(int j = 0;j<=m;j++){
for(int k = 0;k<=n;k++){
if(j < zeros[i] || k < ones[i]) dp[i][j][k] = dp[i - 1][j][k];
else dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - zeros[i]][k - ones[i]] + 1);
}
}
}
return dp[zeros.size() - 1][m][n];
}
};
// 滚动数组
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<int> zeros(strs.size(), 0);
vector<int> ones(strs.size(), 0);
for(int i = 0;i<strs.size();i++){
int zeroCount = 0, oneCount = 0;
for(int j = 0;j<strs[i].size();j++){
if(strs[i][j] == '0') zeroCount++;
if(strs[i][j] == '1') oneCount++;
}
zeros[i] = zeroCount;
ones[i] = oneCount;
}
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for(int j = 0;j<=m;j++){
for(int k = 0;k<=n;k++){
if(j >= zeros[0] && k >= ones[0]) dp[j][k] = 1;
}
}
for(int i = 1;i<zeros.size();i++){
for(int j = m;j>=zeros[i];j--){
for(int k = n;k>=ones[i];k--){
dp[j][k] = max(dp[j][k], dp[j - zeros[i]][k - ones[i]] + 1);
}
}
}
return dp[m][n];
}
};