代码随想录算法训练营第四十三天|● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

最后一块石头的重量 II 

题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

思路：尽可能将石头分成重量相近的两堆，结果一定最小，因此问题可以转换为分割子集。dp[i]的含义是背包容量为i的背包能装下的最大重量，由于题目中最大重量是15000，所以我们申请15001的vector。

注意，结果不是target-dp[target]，尽管和sum-2*dp[target]十分相似，但是结果还是差了1。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001,0);
        int sum=0;
        for(auto i:stones)sum+=i;
        int target=sum/2;
        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. 目标和 - 力扣（LeetCode）

思路：乍一看，确实很难把他当做一个动态规划问题。这里有一个公式推导：本题要如何使表达式结果为target，既然为target，那么就一定有 left组合 - right组合 = target。left + right = sum，而sum是固定的。right = sum - left。公式来了， left - (sum - left) = target 推导出 left = (target + sum)/2 。target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。而且要注意，(target + sum)/2向下取整也是有影响的，比如target=2，sum=5，这样是无解的。同样如果target>sum，也是无解的。

本题特殊之处在于之前的背包问题都是求背包最多装多少东西，本题求装满有几种装法，是组合问题，我实在是想不出如何dp，投降....

dp的产生：有哪些来源可以推出dp[j]呢？只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。同时也要关注dp[0]的初始化问题。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(auto i:nums)sum+=i;
        if(sum<abs(target))return 0;
        if((sum+target)&1)return 0;

        int size=(sum+target)/2;
        vector<int> dp(size+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++){
            for(int j=size;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[size];
    }
};

dp[j]+=dp[j-nums[i]];这个公式很重要，请记住。

一和零  

题目链接：474. 一和零 - 力扣（LeetCode）

思路：尽管这里有两个纬度的“重量”，但是该问题依然是一个01背包问题，因为每一个物品只能取一次。

这里我们定义一个二维dp数组，dp[i][j]表示i个0，j个1最多能有多大的子集。先用count数组统计每个子字符串里有多少个0和1，然后用一个三重for循环计算dp。

注意，二维数组是vector<vector<int>>不是vector<int,vector<int>>，哎老糊涂了。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        vector<vector<int>> count(strs.size(),vector<int>(2,0));

        for(int i=0;i<strs.size();i++){
            for(char a:strs[i]){
                if(a =='0') count[i][0]+=1;
                else count[i][1]+=1;
            }
        }

        for(int i=0;i<strs.size();i++){
            for(int j=m;j>=count[i][0];j--){
                for(int k=n;k>=count[i][1];k--){
                    dp[j][k]=max(dp[j][k],dp[j-count[i][0]][k-count[i][1]]+1);
                }
            }
        }
        return dp[m][n];
    }
};