代码随想录算法训练营Day36||Leetcode1049. 最后一块石头的重量 II 、 494. 目标和 、 474.一和零
一、最后一块石头的重量
这题的思路一开始我想到了让相近质量的石头相碰，但是想不到题解的思路给他分成两队，并且能用转化成背包问题，用一个总质量一半的背包去收集能装的最大质量，剩下的就是另一部分。用后一部分的质量减去前部分的质量即为所求。
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 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-dp[target]-dp[target];}
};二、目标和
这题的求解递推公式的时候就很难理解 。首先是把原数组切割成两个数组，一个为正数集，一个为负数集。正数集+负数集=sum，正数集-负数集=target，然后把负数集=正数集-target带入，得到正数集为（sum+target）/2；
然后dp数组用于记录，target为j时的方法，最后统计dp【j】也就是让dp[j-1]以前叠加起来
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(abs(target)>sum)return 0;if((target+sum)%2==1)return 0;int bagsize=(target+sum)/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];}
};三、一和零
装满背包需要多少样物品
（一）dp[i][j]：装满i个0，j个1的背包需要多少个字符串
（二）递推公式：max(dp[i][j],dp[i-num0][j-num1]+1)（注意这里是物品数，不是0或1的个数，所以是＋1）
（三）遍历顺序：先遍历物品，再遍历背包
这里在遍历物品时，用了迭代器，需要我学习：
for(string str:strs(题干中给的)){
for(char c:str)}
这样就不用特意去找起始位置，也不用防止溢出了。
（四）初始化：同前面，为了让max能替换，一开始设为非负最小值0即可。
（五）返回最后一个dp[m][n]
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 num0=0;int num1=0;for(char c:str){if(c=='0')num0++;else num1++;}for(int i=m;i>=num0;i--){for(int j=n;j>=num1;j--){dp[i][j]=max(dp[i][j],dp[i-num0][j-num1]+1);}}}return dp[m][n];}
};