Day42&&43——分割等和子集、1049. 最后一块石头的重量 II 494. 目标和 474.一和零 （动规）

断了很久了，疲惫，垃圾期末

目录

前言

一、分割等和子集

解题思路：

二、最后一块石头的重量 II

解题思路：

三、目标和

解题思路：

四、一和零

解题思路：

总结

前言

人生就是这样，总有一天会明白一切，只是这时候再不能回到以前。人生，有时候，就是想大哭一场，因为心里憋屈。有时候，就是想疯癫一下，因为情绪低落。有时候，就是想破口大骂，因为心里不爽。有时候，就是想安安静静，因为真的我累了

一、分割等和子集

力扣

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解题思路：

数组的元素能不能对半分成等和集合，那就是背包能不能装到数组元素和的一半，价值=空间，装满的时候是不是等于目标值。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int>dp(10001,0);
        
        int sum=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];                //求出和
        }
        int target=sum/2;            //一半，是空间也是目标价值
        if(sum%2!=0)                //如果是奇数都没有办法分成两份，直接错了
        {
            return false;
        }

        for(int i=0;i<nums.size();i++)                //遍历物品
        {    
            for(int j=target;j>=nums[i];j--)        //遍历背包，从后往前
            dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);    //找出最大值
        }
        if(dp[target]==target)    //因为价值等于容量，背包装满的时候，理论上价值也会一样
        return true;
        return false;
    }
};

二、最后一块石头的重量 II

力扣

解题思路：

和上面差不多，就是分两拨，求出target容量最多能装多少，然后一堆是dp[target],另外一堆是sum-dp[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(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 - dp[target] - dp[target];
    }
};

三、目标和

力扣

解题思路：

正数和+负数和=sum  正数和-负数和=target 那么正数和=(sum+target)/2，那就是装满正数和容量背包的方法有多少种。

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<abs(target))        //记得加绝对值
        {
            return 0;
        }
        if((target+sum)%2==1)        //单、双数就g
        {
            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]+dp[j-nums[i]];
            }
        }
        return dp[bagsize];
    }
};

四、一和零

力扣

解题思路：

背包有两个容量，0和1。然后从这两个角度考虑装进的最多的元素。

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 x=0,y=0;
            for(char c:str)            //拆每一个字符串
            {
                if(c=='0')            //找到0和1的数量代表物品的体积
                {
                    x++;
                }
                if(c=='1')
                {
                    y++;
                }
            }
            for(int i=m;i>=x;i--)        //背包的容量，0和1为背包容量，两种
            {
                for(int j=n;j>=y;j--)
                {
                    dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1); //要是装入就+1
                }
            }
        }
        return dp[m][n];
    }
};

总结

考虑好，难，只能说