代码随想录算法训练营Day38|1049. 最后一块石头的重量 II ， 494. 目标和 ， 474.一和零

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;int n=stones.size();
        for(int i=0;i<n;i++) sum+=stones[i];
        int target=sum/2;
        vector<int> dp(1501,0);
        for(int i=0;i<n;i++){
            for(int j=target;j>=stones[i];j--){
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return fabs(sum-2*dp[target]);
    }
};

494. 目标和：代码随想录

这道题目的意思就是给你一个整数数组nums还有一个数字target，他让你将一些数变成负数，然后让整个数组的元素的和等于target，问你有多少种方法，那么这样的一道题，我们怎么用背包问题来解决呢，这里我先假设一共有元素和为p的数是不加负号的，那也就是说有另外的sum-p的元素和是要加上负号的，那整个数组的元素和就是p-(sum-p)注意这里中间的代表的是加上负号的意思，实际上你也可以写成这样更方便理解，p + -(sum-p)=target，这样再转化一下就是2p=target+sum，也就是p=(target+sum)/2;这样我们是不是就将其转化为了一个背包问题了，就是从数组中取数，将容量为这么多的背包装满有多少种方法，明确了这一点，直接上动规五部曲

1.dp数组以及其下标的含义：

        dp[j] 表示的就是将容量为j的背包装满有多少种不同的方法

2.递推公式：

        这里我是要求一共有多少种方法，而不是像之前一样求最大的价值，所以这里我们来分析一下，你想想看，只要我们明确了nums[i],我们就可以确定有dp [ j - nums[i] ] 种方法，这里你可能有一点迷惑，我们再来看看dp数组的定义是什么，dp数组的定义是将背包容量为j的背包装满一共有多少种方法，那么这里我的j是此时背包的容量，那么nums[i]代表的就是当前元素的值，而j - nums[i]代表的就是装满这么多的背包一共有多少种方法，所以此时你懂了吗，但是这只是一种情况，因为外层循环的nums[i]是会不断地变化的，所以这里是要不断的累加的，故得出递推公式为：dp[j] += dp[j-nums[i]];

3.dp数组的初始化：

        这里你想想看当我的背包容量为0时，我的dp数组的值应该等于多少，有人觉得应该等于0，真的是等于0吗，这么说过去好像说得通，就是什么都不加就是0，但是我们初始化要看的是题目的意思，而不是自己想，假设nums={0} ，targe=0，这样dp数组的值还是0吗，很明显不是吧，所以我们的dp[0]应该要初始化为1

4.dp数组的遍历顺序：

        和前面的题目一样，外层循环从前往后，内层循环从后往前，因为值会被覆盖掉，因为这里进行了状态压缩，使用的是滚动数组

下面来看具体的代码的实现：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;int n=nums.size();
        for(int i=0;i<n;i++) sum+=nums[i];
        sum+=target;
        if(sum<0 || sum%2!=0) return 0;
        vector<int> dp(10001,0);
        dp[0]=1;
        target=sum/2;
        //dp数组的含义：有dp[i]种方法装满容量为i的背包
        for(int i=0;i<n;i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];
    } 
};

注意这里如果一开始就不能整除的话，就可以直接返回0了，代表没有方法，这里再分享一下另一种做法

class Solution {
public:
    int dfs(int i, int c, vector<int>& nums){
        if(i<0){
            if(c==0) return 1;
            else return 0;
        }
        else if(c<nums[i]){
            return dfs(i-1,c, nums);
        }
        else {
            return dfs(i-1,c, nums)+dfs(i-1,c-nums[i], nums);
        }
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        target+=sum;
        int n=nums.size();
        if(target<0 || target%2!=0) return 0;
        else{
            target/=2;
            return dfs(n-1,target, nums);
        }
    }
};

这里是利用dfs的方法递归调用的，我们就是只来看看dfs内部的部分，其他的都是差不多的，这里的i代表的就是数组的下标当i小于0时，代表已经没有物品可以选了，此时如果c也恰好为0，则代表找到了一种情况，就返回1，否则返回0，接着就是如果当前的元素都已经大于我的c了那肯定是不选，就直接让下标减一再返回并且这里c是不变的，因为没有选，如果不是的话，就是返回选与不选的和因为这里是求所有的情况，选或者是不选都有可能满足条件相加返回即可

接着在主函数中调用传入参数n-1，和target即可，这就是这道题目的解答

474.一和零: 代码随想录

这道题目的意思就是给你一个字符串数组nums，然后给你一个m和n分别表示子集中0和1的最大数量，让你找到一个子集，这个子集中最多有m个0和n个1，那么这样一个问题我们怎么用背包的思想来思考呢，其实这里只是将背包的容量提升到了两个维度，也就是1和0的数量，其他的都是不变的，明确了这一点我们直接来上动规五部曲

1.dp数组以及其下标的含义：

        这里注意我们虽然仍然是状态压缩，也就是用滚动数组，但是重点是我们这里重量是有两个维度的，也就是说明只用一个一维数组是不够的，所以这里我们要用一个二维数组来表示，i，j就是分别表示0的最大数量和1的最大数量，dp[i][j]就是代表一个子集的最大的长度，在1的个数最多为n和0的个数最多为m的情况之下

2.递推公式：

        这里对比以前的01背包，递推公式是一样的，只不过有两个维度需要考虑，这里的x，y分别表示当前遍历的字符串里的0个数和1的个数，也就是相当于之前的nums[i],所以递推公式就是dp[i][j]=max(dp[i][j] , dp[i - x][j - y] + 1) ,注意这里的价值就是子集的个数后面的加1代表选，选的话子集的个数必然要加1

3.dp数组初始化：

        这里当i，j为0时，必然都为0，所以全部初始化为0即可

4.遍历顺序：

        这里需要着重强调的是，即使我这里用的是二维数组，我任然是滚动数组，也就是最外层循环遍历的是数组里的字符串元素，内层遍历的是0和1两个维度，即使是两层循环在内部，任然是要从后往前遍历，因为如果是从前往后遍历会覆盖掉元素

来看具体的代码的实现：

class Solution {
public:
    int findMaxForm(vector<string>& nums, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(string s:nums){
            int x=0;int y=0;
            for(char c:s){
                if(c=='0') x++;
                else y++;
            }
            for(int i=m;i>=x;i--){
                for(int j=n;j>=y;j--){
                    dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
                }
            }
        }
        return dp[m][n];
    }
};

最后返回dp[i][j]即可，以上就是今天的全部内容了，继续努力吧！