笔记：代码随想录算法训练营day36:LeetCode1049. 最后一块石头的重量 II、494. 目标和、474.一和零

学习资料：代码随想录

1049.最后一块石头的重量II

力扣题目链接

思路：如何讲该问题转化为背包问题：还是对半分去碰，对半分去碰碰剩下的就是最小的。然后背包容量就是一半儿，物品重量等于物品价值等于stones[i]

和上一题不同的是return什么，这里返回碰完后的值即（sum-target）-（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(30*100/2+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]);
                //cout<<dp[j];
            }
        }
        
        return (sum-dp[target])-dp[target];
    }
};

494.目标和

力扣题目链接

如何将该题转换成背包问题，有一个小推导，假如分出来的正数是x，那么分出来的负数就是-（sum-x），两数相加等于target，就是x-(sum-x) = target;

交换一下，x = (target+sum)/2

求的结果是方法数，那么x为背包容量，物品的重量等于物品的价值等于nums[i]

定义：dp[i][j] 的表示前i个数能够满足：选子集（可以选0个数）求和等于x的方法数量

递推公式：dp[i][j]等于不放物品i正好满足j 的方法+放i（需要把i的容量先让出来）正好满足j的方法

初始化：第一行，当然0，0处不放是一种方法，然后如果物品0能满足背包容量为k的话，在0，k处方法应该也是1

在左侧第一列，需要处理一种特别有意思的情况，即物品的重量为0（nums[i]=0）,该物品能够满足背包容量为0的情况。前面有record个num[i] = 0的情况，那么总的方法会变成2的record次方，注意这个方法是会累计的 ，遇到num[i]=0就累积，如果遇到num[i]!=0,就不累计了，但是可别错误得改成1.   

遍历顺序：第一列已经初始化过了，但从0开始遍历也没有问题，因为本行是由上一行推导的出的

打印：略

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 || abs(target)>sum){     //细节
            return 0;                     //你看嗷，如果x不是整数，不就说明没办法构造吗
        }

        int x = (target+sum)/2;
        vector<vector<int>> dp(nums.size(),vector<int>(x+1,0));

        // 第一行
        if(nums[0]<=x){
        dp[0][nums[0]] = 1;
        }
        // 第一列  
        int record = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                record++;
                //cout<<record<<endl;
            }
                //dp[i][0] = 2^record;    //每一个值为0的数字都有选与不选两种状态
            dp[i][0] = (int) pow(2.0,record);
        }

        for(int i=1;i<nums.size();i++){
            for(int j=1;j<=x;j++){
                if(nums[i]>j) dp[i][j] = dp[i-1][j];
                else{
                dp[i][j] = dp[i-1][j] +dp[i-1][j-nums[i]];  //不放物品i的方法+放物品i的方法（空出i的值）
                //cout<<dp[i][j]<<endl;
                }
            }     
        }

        return dp[nums.size()-1][x];
    }
};

debug了好久

压缩成一维，初始化dp[0]为1就可以了，如果第一个物品重量为0的话还可以在递推公式中处理掉

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 || abs(target)>sum){     //细节，没有abs，在测试用例为nums=100，target=-200时报错
            return 0;                     //你看嗷，如果x不是整数，不就说明没办法构造吗
        }

        int x = (target+sum)/2;
        vector<int> dp(x+1,0);

        dp[0] = 1;         //放第一个物品时，先把不放物品的这一种情况加上，后面递推可以根据nums[0]的值来调整

        for(int i=0;i<nums.size();i++){
            for(int j=x;j>=nums[i];j--){
                dp[j] = dp[j] +dp[j-nums[i]];  //不放物品i的方法+放物品i的方法（空出i的值）
                //cout<<dp[i][j]<<endl;
            }     
        }
        return dp[x];
    }
};

474.一和零

力扣题目链接

定义：dp[i][j]为最多i个0，j个1的子集大小

递推公式：将每一个strs中的一个字符串看作是一个物品，物品重量分别为0的个数和1的个数，价值为1（代表是子集的一个组成部分）

初始化：由于value都是1，初始化一个小一点的数，0就可以了

遍历顺序：按一维dp来

打印：略

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 zeroNum = 0;int oneNum = 0;
            for(char s:str){
                if (s=='0') zeroNum++;
                else{oneNum++;}             //Calculate the weight of every str
            }
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
                    dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);     //value[str] = 1；这句是放与不放str的值的对比
                }
            }
        }
       return dp[m][n]; 
    }
};