代码随想录算法训练营day42

题目：1049. 最后一块石头的重量 II 、494. 目标和、474.一和零

参考链接：代码随想录

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

思路：本题石头是相互粉碎，粉碎后剩下的重量就是两块石头之差，我们可以想到，把石头分成两堆总重量分别为A和B，则这两堆相互粉碎后，剩下的就是这两堆的重量之差，我们需要使得这个差尽可能小，即把石头尽可能分为两部分，使得他们重量差最小。然后和01背包问题对应起来，物品的重量就是石头的重量stones[i]，物品的价值也是石头的重量stones[i]，背包的容量最大为重量和除以2，因为这样使背包尽可能装满，二者的差就会最小。dp五部曲：dp数组，dp[j]表示容量为j的背包能装的最大重量；递推公式，和之前一样，当i能装进去的时候，dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])；dp初始化，首先全部初始化为0，和上题一样；遍历顺序，对物品从0-i遍历，但对背包容量需要从大到小遍历；举例略。时间复杂度O(mn)，m为总重量。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=accumulate(stones.begin(),stones.end(),0);
        int target=sum/2;
        vector<int> dp(target+1,0);//初始化dp数组
        for(int i=0;i<stones.size();i++){
            for(int j=target;j>=0;j--){
                if(stones[i]<=j){
                    dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
                }
            }
        }
        return sum-dp[target]*2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

关键在于如何把本题和01背包问题联系起来。

494. 目标和

思路：本题初看就是回溯法的组合总和，但是会超时。然后想想dp的方法，所有数前面只有+和-两种情况，我们设+的总和为x，则-的总和为sum-x，最后得到x-(sum-x)=2x-sum=target，故x=(sum+target)/2，我们把x当做背包容量，然后把x装满即可，需要求的是把容量为x的背包装满用的方法数量，其中weight和value都为nums。对x的计算，考虑取整问题，由于2x=sum+target，故sum和target必须奇偶性相同，如果不同则无解，直接排除，还有target的绝对值不可能大于sum，不然也无解，这两种情况都需要先排除。然后是方案的计算方法，本题也是一个元素只能放一次，故也是01背包问题，但是求解的东西不一样，01背包求的是最大价值，这里求的是方法数，故我们的dp数组需要有变化。五部曲：dp数组，dp[j]表示容量为j的背包装满的最大方法数；递推公式，还是和之前的方法思考，如果物品i不能最先放进去，那么就没有新的方法产生，方法数还是原来的dp[j]，如果物品i可以先放进去，那么方法就需要在原有的基础上增加dp[j-nums[i]]，故dp[j]+=dp[j-nums[i]]；dp初始化，首先如果全部初始化为0，则递归后全部都是0，明显不符合，对于dp[0]，不能初始化为0
只能初始化为1，即背包完全不放，也是一种方法，对其他dp[j]，递推公式都是从dp[0]慢慢累加起来的，我们初始化为1；遍历顺序，和之前相同；举例，这种不好想的题目，还是得举例的，nums=[1,1,1,1,1]，target=3，x=4，dp初始化为[1,0,0,0,0]，当i=0时，dp由递推公式计算的[1,1,0,0,0]，i=1时，[1,2,1,0,0]，i=2时，[1,3,3,1,0]，i=3时，[1,4,6,4,1]，i=4时，[1,5,10,10,5]，最终答案为5，符合。时间复杂度O(mn)。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if((sum+target)%2==1||abs(target)>sum){
            return 0;
        }
        int x=(sum+target)/2;
        vector<int> dp(x+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++){
            for(int j=x;j>=0;j--){
                if(nums[i]<=j){
                    dp[j]+=dp[j-nums[i]];
                }
            }
        }
        return dp[x];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

本题的几个重点，首先是根据每个元素放一次想到01背包问题，然后是将正负分开计算得出背包容量，这里类似上题的一分为二，只考虑一部分就是背包容量，最后是dp数组的定义，需要根据题目所求灵活设置。
本题的递推公式dp[j]+=dp[j-nums[i]]常用于求背包中方法数。

474.一和零

思路：本题初看一点想法都没有，只想到纯暴力方法，把所有子集列出来，再计算0和1的个数。直接看解答，首先要弄明白几种背包问题的区别。

strs里数组的元素就是物品，每个物品只有一个，m和n相当于一个背包，只不过这个背包有两个维度，即两个维度都不能超过容量，物品的weight也有两个维度，分别是0和1的数量，value可以全部认为是1，因为要求集合元素数最大。这里如果按照最初始的01背包问题，需要三维数组，这里我们还是压缩一维，使用二维数组。五部曲：dp数组，dp[i][j]表示背包中最多物品的数量，其中0的个数不超过i，1的个数不超过j；递推公式，设物品k中0和1的数量分别为zeroNum和oneNum，则如果物品k能先放进去背包时，dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)；初始化，对dp[0][0]，物品数量为0，我们可以就全部初始化为0，这个和普通的01背包是一个意思；遍历顺序，从背包容量大到小遍历；举例略。时间复杂度O(kmn)，k为strs长度。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));//初始化全为0
        for(int k=0;k<strs.size();k++){
            int zeroNum=0,oneNum=0;
            for(char c:strs[k]){
                if(c=='0'){
                    zeroNum++;
                }
                if(c=='1'){
                    oneNum++;
                }
            }
            for(int i=m;i>=0;i--){
                for(int j=n;j>=0;j--){
                    if(zeroNum<=i&&oneNum<=j){
                        dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                    }
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25