【代码随想录|动态规划背包问题应用】
1049.最后一块石头的重量
题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）
因为这里是求石头相撞留下来最小的重量，就可以用背包问题来解，把所有石头尽量分成重量相同的两堆，然后再相减，就是留下来最小的重量了
相撞完一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
把他们相减就是要返回的sum-2*dp[target];
动规五部曲：
1、确定dp数组的含义：dp[j] 表示容量为j的背包，可以装的最大价值为dp[j]这个数
2、确定递推公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
3、确定dp数组如何初始化：
题目条件是
1 <= stones.length <= 301 <= stones[i] <= 100
那在最大的情况下我的target也就是所有石头加起来的重量/2的值应该是30*100/2=1500的大小，再算上我们算背包容量是从0开始算的所以dp数组的大小就可以设置为1501。
背包容量为0的时候肯定啥都装不下，为了方便都设置为0
4、确定遍历顺序
从前往后遍历物品，从后往前遍历价值。
5、（打印dp数组）
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum=accumulate(stones.begin(),stones.end(),0);
int target=sum/2;
vector<int> dp(1501,0);
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-2*dp[target];//两堆石头的差值
}
};494.目标和
题目链接：494. 目标和 - 力扣（LeetCode）
（我的妈呀，没想到这道题考虑的点要那么多，aaa奥利给）
二维的做法，我觉得用二维的做法理解一遍的一维的好理解很多
思路我觉得顺着是这么想的：因为我的数组加加减减得到target，那不如直接把加整合成一个集合，把要减的整合成一个集合，然后用加的集合减去要减的集合的数值就是target
因为left+right=sum;
left-right=target;
left = (target + sum)/2
就是因为在这个背包问题中，一旦确定了加法部分的子集和（即 +num 的子集和），那么减法部分（即 -num 的子集和）也自然就确定了，因此，求得加法部分的子集和的组合方式数就是整个问题的解。
1、确定dp数组的含义：
dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j这么大容量的包，有dp[i][j]种方法。
2、确定递归公式：
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
不放物品是dp[i - 1][j]
放物品是 dp[i - 1][j - nums[i]];就是空出来这个物品的容量的的组合方式数，因为我放这个方法就是直接在空出来这个物品的容量的的组合方式数上面叠加，所以值是一样的。
3、dp数组的初始化
dp[0][0]的值，装满背包容量为0 的方法数量是1，即 放0件物品。
因为我要确定他加的值就是那么多，所以我的背包必须要装满，才算是一种方式，如果你都装不满了，那能实现的方式就为0
其他情况下，要不是装不满，要不是装不下。
所以初始化：dp[0][nums[0]] = 1 ，其他均为0
而表格最左列就设置为0就好，因为背包容量为0就肯定为0了（但是为了防止nums为0的情况：
如果有两个物品，物品0为0， 物品1为0，装满背包容量为0的方法有几种。
- 放0件物品
- 放物品0
- 放物品1
- 放物品0 和 物品1
此时是有4种方法。
其实就是算数组里有t个0，然后按照组合数量求，即 2^t 。）
4、确定遍历顺序：
从左到右，从上到下，二维数组推就行内外层for循环交换位置也没关系
5、（打印dp数组）
class Solution {//二维dp数组做法
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 == 1)
return 0;
if (abs(target) > sum)
return 0;
int bagsize = (sum + target) / 2;
vector<vector<int>> dp(nums.size(), vector<int>(bagsize + 1, 0));
dp[0][0] = 1;
dp[0][nums[0]] = 1;
int zero = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0)
zero++;
dp[i][0] = pow(2, zero);
}
for (int i = 1; i < nums.size(); i++) {
for (int j = 1; j < bagsize + 1; j++) {
if (j < nums[i])
dp[i][j] = dp[i - 1][j];
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
return dp[nums.size() - 1][bagsize];
}
};一维的做法，感觉就不用像二维一样管太多初始化，嘎嘎往上敲就行
class Solution {//一维dp数组的做法
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 == 1)
return 0;
if (abs(target) > sum)
return 0;
int bagsize = (sum + target) / 2;
vector<int> dp(bagsize+1,0);
dp[0]=1;
for(int i=0;i<nums.size();i++){
for(int j=bagsize;j>=nums[i];j--){//从后往前遍历
dp[j]+=dp[j-nums[i]];
}
}
return dp[bagsize];
}
};474.一和零
题目链接：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 zero=0,one=0;
for(char c:str){
if(c=='0')zero++;//str是字符串所以一定要判断c=='0'不是c==0
else one++;
}
for(int i=m;i>=zero;i--){
for(int j=n;j>=one;j--){
dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1);
}
}
}
return dp[m][n];
}
};这里的思路就是我先遍历物品，算出来每个字符串的0和1的值，然后再计算每一个物品中，从背包容量遍历到我能放下的容量为止，计算我能放下该字符串的子集数目，最后返回的dp[i][j]就是最多有i个0和j个1的的最大子集的大小
递推公式：dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1);
递推公式的意思 因为题目要返回最大的子集长度，所以比较我不放这个字符串（dp[i][j]）和放这个字符串（dp[i-zero][j-one]+1）选最大的
放字符串的意思是：在不放这个字符串（zero 个0，one 个一）的时候的子集数目加1，代表我要在里面放这个字符串