好久不见，兄弟们，我终于把期末考试考完了，现在已经放暑假回家了，开始恶补算法了，那么废话不多说，来看今天的内容
1049. 最后一块石头的重量 II：代码随想录
这道题目的意思就是给你一个数组表示每个石头的重量，只要两个石头相撞，重量小的重量变为0，大的就要减去小的重量，为你撞到只剩最后一个石头的时候，他的最小的重量为多少，其实这题也是一样的，我们要尽可能的将所有的石头分成相同的重量的两堆，这样的话撞完之后，所剩下的重量就是最小的，所以这题首先就是先求出所有石头的重量的总和，然后定义一个target等于sum除以2，然后这个背包的容量就是target，我们要做的就是从这个数组中找到石头他们的重量加起来尽可能的等于target，下面直接来上动规五部曲
1.dp数组以及其下标的含义：
dp[i]就是容量为i的背包所装的最大重量的物品，注意这里的价值就是物品的重量。
2.递推公式：
dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
3.dp数组初始化：
当背包的容量为零时，所装的物品的最大价值为0，其余的都是由递推公式推导而来，由于要娶最大值，所以全部要初始化为0，一避免被覆盖
4.遍历顺序：
由于这里我进行了状态压缩，使用的时滚动数组，所以外层循环遍历的时物品，内层循环遍历的时背包的容量，外层循环是从前往后，因为是由上一个状态推导而来，而遍历被背包的时候，你想想看，我这个当前遍历的值是由左上角和上方的值推导而来的，所以如果我也是从前往后遍历的话，那原来的值就会被覆盖，因为我这个是滚动数组，所以我这里就要从后往前遍历，为了避免值被覆盖
说完了这些，下面我们来看具体的代码的实现
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum=0;int n=stones.size();
for(int i=0;i<n;i++) sum+=stones[i];
int target=sum/2;
vector<int> dp(1501,0);
for(int i=0;i<n;i++){
for(int j=target;j>=stones[i];j--){
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return fabs(sum-2*dp[target]);
}
};注意在最后的时候，由于我这个/是向下取整的，所以我剩余的元素的和一定是大于等于这个dp[target] 的值的，所以我就直接返回他们两个的差值就可以了。来看下一题
494. 目标和：代码随想录
这道题目的意思就是给你一个整数数组nums还有一个数字target，他让你将一些数变成负数，然后让整个数组的元素的和等于target，问你有多少种方法，那么这样的一道题，我们怎么用背包问题来解决呢，这里我先假设一共有元素和为p的数是不加负号的，那也就是说有另外的sum-p的元素和是要加上负号的，那整个数组的元素和就是p-(sum-p)注意这里中间的代表的是加上负号的意思，实际上你也可以写成这样更方便理解，p + -(sum-p)=target，这样再转化一下就是2p=target+sum，也就是p=(target+sum)/2;这样我们是不是就将其转化为了一个背包问题了，就是从数组中取数，将容量为这么多的背包装满有多少种方法，明确了这一点，直接上动规五部曲
1.dp数组以及其下标的含义：
dp[j] 表示的就是将容量为j的背包装满有多少种不同的方法
2.递推公式：
这里我是要求一共有多少种方法，而不是像之前一样求最大的价值，所以这里我们来分析一下，你想想看，只要我们明确了nums[i],我们就可以确定有dp [ j - nums[i] ] 种方法，这里你可能有一点迷惑，我们再来看看dp数组的定义是什么，dp数组的定义是将背包容量为j的背包装满一共有多少种方法，那么这里我的j是此时背包的容量，那么nums[i]代表的就是当前元素的值，而j - nums[i]代表的就是装满这么多的背包一共有多少种方法，所以此时你懂了吗，但是这只是一种情况，因为外层循环的nums[i]是会不断地变化的，所以这里是要不断的累加的，故得出递推公式为：dp[j] += dp[j-nums[i]];
3.dp数组的初始化：
这里你想想看当我的背包容量为0时，我的dp数组的值应该等于多少，有人觉得应该等于0，真的是等于0吗，这么说过去好像说得通，就是什么都不加就是0，但是我们初始化要看的是题目的意思，而不是自己想，假设nums={0} ，targe=0，这样dp数组的值还是0吗，很明显不是吧，所以我们的dp[0]应该要初始化为1
4.dp数组的遍历顺序：
和前面的题目一样，外层循环从前往后，内层循环从后往前，因为值会被覆盖掉，因为这里进行了状态压缩，使用的是滚动数组
下面来看具体的代码的实现：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum=0;int n=nums.size();
for(int i=0;i<n;i++) sum+=nums[i];
sum+=target;
if(sum<0 || sum%2!=0) return 0;
vector<int> dp(10001,0);
dp[0]=1;
target=sum/2;
//dp数组的含义：有dp[i]种方法装满容量为i的背包
for(int i=0;i<n;i++){
for(int j=target;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[target];
}
};注意这里如果一开始就不能整除的话，就可以直接返回0了，代表没有方法，这里再分享一下另一种做法
class Solution {
public:
int dfs(int i, int c, vector<int>& nums){
if(i<0){
if(c==0) return 1;
else return 0;
}
else if(c<nums[i]){
return dfs(i-1,c, nums);
}
else {
return dfs(i-1,c, nums)+dfs(i-1,c-nums[i], nums);
}
}
int findTargetSumWays(vector<int>& nums, int target) {
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
target+=sum;
int n=nums.size();
if(target<0 || target%2!=0) return 0;
else{
target/=2;
return dfs(n-1,target, nums);
}
}
};这里是利用dfs的方法递归调用的，我们就是只来看看dfs内部的部分，其他的都是差不多的，这里的i代表的就是数组的下标当i小于0时，代表已经没有物品可以选了，此时如果c也恰好为0，则代表找到了一种情况，就返回1，否则返回0，接着就是如果当前的元素都已经大于我的c了那肯定是不选，就直接让下标减一再返回并且这里c是不变的，因为没有选，如果不是的话，就是返回选与不选的和因为这里是求所有的情况，选或者是不选都有可能满足条件相加返回即可
接着在主函数中调用传入参数n-1，和target即可，这就是这道题目的解答
474.一和零: 代码随想录
这道题目的意思就是给你一个字符串数组nums，然后给你一个m和n分别表示子集中0和1的最大数量，让你找到一个子集，这个子集中最多有m个0和n个1，那么这样一个问题我们怎么用背包的思想来思考呢，其实这里只是将背包的容量提升到了两个维度，也就是1和0的数量，其他的都是不变的，明确了这一点我们直接来上动规五部曲
1.dp数组以及其下标的含义：
这里注意我们虽然仍然是状态压缩，也就是用滚动数组，但是重点是我们这里重量是有两个维度的，也就是说明只用一个一维数组是不够的，所以这里我们要用一个二维数组来表示，i，j就是分别表示0的最大数量和1的最大数量，dp[i][j]就是代表一个子集的最大的长度，在1的个数最多为n和0的个数最多为m的情况之下
2.递推公式：
这里对比以前的01背包，递推公式是一样的，只不过有两个维度需要考虑，这里的x，y分别表示当前遍历的字符串里的0个数和1的个数，也就是相当于之前的nums[i],所以递推公式就是dp[i][j]=max(dp[i][j] , dp[i - x][j - y] + 1) ,注意这里的价值就是子集的个数后面的加1代表选，选的话子集的个数必然要加1
3.dp数组初始化：
这里当i，j为0时，必然都为0，所以全部初始化为0即可
4.遍历顺序：
这里需要着重强调的是，即使我这里用的是二维数组，我任然是滚动数组，也就是最外层循环遍历的是数组里的字符串元素，内层遍历的是0和1两个维度，即使是两层循环在内部，任然是要从后往前遍历，因为如果是从前往后遍历会覆盖掉元素
来看具体的代码的实现：
class Solution {
public:
int findMaxForm(vector<string>& nums, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(string s:nums){
int x=0;int y=0;
for(char c:s){
if(c=='0') x++;
else y++;
}
for(int i=m;i>=x;i--){
for(int j=n;j>=y;j--){
dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
}
}
}
return dp[m][n];
}
};最后返回dp[i][j]即可，以上就是今天的全部内容了，继续努力吧！
