代码随想Day43 | 1049. 最后一块石头的重量 II、494. 目标和、474.一和零

本题和昨天的?416.?分割等和子集很像，转化思路为，尽量将石头分成两堆重量相同的石头堆，给定包的容量，尽可能多的装能装多少重量，这样两堆相碰最终得到的就是做小石头重量，于是就和416很像，唯一不同的是最后的判断逻辑，最小的石头重量等于sum-dp[target]-dp[target]。

dp[j]：容量为j的背包的最大价值，这道题的价值和重量相同。

递推公式：dp[j]=max(dp[j],dp[j-stone[i]]+stone[i]。

遍历顺序：背包倒序，保证每个物品只放一次。

详细代码如下：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int stone:stones)
        {
            sum+=stone;
        }
        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-2*dp[target];

    }
};

494.?目标和?

这道题目的思路是分为加法的集合和减法的集合两队，然后根据题目可以求出，加法的集合的总和应该为sum+target的一半，问题转化为有多少方法可以装满容器。

dp[j]：装满背包容量为j的方法总数。

递推公式：思路类似爬楼梯的题目，详细的分析在代码随想录，最终得到递推公式为

dp[j]+=dp[j-nums[i]]；(所有求装满背包的多少种方法的公式)

初始化：dp[0]=1。

详细代码如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //分为加法和减法的集合
        int  sum=0;
        for(int num:nums) sum+=num;
        int add = (target+sum)/2;
        if((target+sum)%2==1) return 0; //凑不成目标和
        if(add<0) return 0;   //注意加法的集合不可以小于0
        vector<int>dp(add+1,0);
        dp[0]=1; //初始化
        for(int i=0;i<nums.size();i++)
        {
            for(int j=add;j>=nums[i];j--)
            {
                dp[j]+=dp[j-nums[i]]; //求装满背包有多少种方法的公式
            }
        }
        return dp[add];

    }
};

474.一和零??

这道题是背包问题的另一个维度应用，给定了背包的容量m个0和n个1，问最多能装多少个物品，每个物品的重量就是x个0和n个1。

这个背包是二维的，dp[i][j]表示装满i个0j个1最多的物品数。

递推公式：取放这个物品和不放这个物品的最大物品数，dp[i][j]=max(dp[i][j]，dp[i-x][j-y]+1)，注意等式右边的dp[i][j]是遍历完上一个物品的最大物品数，因此不放当前物品的话就直接是这个。

初始化：当容量为0和0和0个1时，最多的物品是0个,dp[0][0]=0；

遍历顺序：先物品再背包，注意背包有两个维度，背包的两个维度没有先后顺序，可以颠倒。

详细代码如下：

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 one=0,zero=0;
            for(char s:str)
            {
                if(s=='0')zero++;
                else one++;
            }
            for(int i=m;i>=zero;i--)
            {
                for(int j=n;j>=one;j--)
                {
                    dp[i][j] = max(dp[i][j],dp[i-zero][j-one]+1);//最多有多少个物品
                }
            }
        }
        return dp[m][n];

    }
};