代码随想录训练营day36|1049.最后一块石头的重量II，494.目标和，474.一和零
1049.最后一块石头的重量II
timu
思路：首先是01背包，因为每块石头只能用一次，（新产生的石头也不是原来的）。背包的体积是石头的总重量。价值是粉碎的石头重量，要想办法让价值最大化，这样剩下来的石头就最轻。dp[i][j]是空间为j时的背包，它可以选择粉碎不粉碎第i块石头，这样它的价值就和dp[i-1][j]一样，也可以选择粉碎：dp[i][j]=dp[i-1][j-2weight[i]]+2weight[i]
草，思路好像错了，应该是把石头分成尽可能重量相接近的两堆，这样就能使得剩余重量最少。
//j是背包能装的最大重量，dp[i][j]是当前背包实际装的最大重量，
//最后用sum_weight-2*dp[i-1][m];
int m=sum/2;
int n=stones.size()
//小的那一堆
vector<vector<int>> dp(n,vector<int>(m+1,0));
for(int j=nums[0];j<m+1;j++){
dp[0][j]=nums[0];
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(j-nums[i]>=0)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
else
dp[i][j]=dp[i-1][j];
}
}
return sum_weight-2*dp[stones.size()-1][sum_weight/2];
494.目标和
题目
思路我一开始想的还是对的，就是找（sum-target）/2的数组，但是我在dp[i][j]的含义上没定义好，我定义的仍然是当前最大的重量，但应该是能装满当前j空间的方法数。
dp[i][j]要想装满只有两种方法，要么不装nums[i]，这样它的方法数就等于dp[i-1][j]
要么装上nums[i]，这样就要把j-nums[i]的空间填满，所以
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
本题的另一个难点在于如何初始化，首先dp[0][0]应该初始化为1，因为对于容量为0的背包什么都不做就能把它装满，然后dp[0][nums[0]]=1
只有它能恰好用nums[0]装满
然后就是第0列的初始化，应该统计0，i之间有几个0，因为只要有n个0，就有pow(2，n)种办法，既可以填+也能填-。
for(int j=1;j<target_2+1;j++){
if(j==nums[0]){
dp[0][j]=1;
break;
}
}
dp[0][0]=1;
int numZero = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) numZero++;
dp[i][0] = (int) pow(2.0, numZero);
}
//装满空间为0的背包什么都不用做
for(int i=1;i<n;i++){
for(int j=1;j<target_2+1;j++){
if(j-nums[i]>=0)
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
else
dp[i][j]=dp[i-1][j];
}
}
return dp[n-1][target_2];
如果用一维数组的话，在nums[0]==0时，也要dp[0]=2；
一和0
题目
题目要求有最多m个0和n个1，那它就有两个维度了，
之前只有一个比较维度是可以用滚动数组实现，现在要用二维数组
dp[i][j]中的i是最多有多少个i个0，j是最多有j个1，dp[i][j]的含义是当前条件下最长的子集数量（value）
假设当前子串有x个0，y个1
则dp[i][j]=max（dp[i-x][j-y]+1，dp[i][j]）;
可以类比纯01背包中dp[j]=max（dp[j]，dp[j-weight[i]]+value[i]）;
只不过这里每个的value都是1.
先遍历物品，再遍历背包，需要注意的是背包需要倒叙遍历，这样才能确保每个物品只用了一次。
(正序的话do[i-x][j-y]取的最长子集有可能就是包含了放入x和y的情况，会重复)
vector<vector<int>> dp(m+1,vector<int> (n+1,0));
//m=1时需要0，1两种选择。
dp[0][0]=0;
for(int str=0;str<strs.size();str++){
string s=strs[str];
int x=0,y=0;
for(char a:s){
if(a=='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];