代码随想录算法训练营第60期第三十九天打卡

        大家好，我们今天继续讲解我们的动态规划章节，昨天我们讲到了动态规划章节的背包问题，昨天讲解的主要是0-1背包问题，那么今天我们可能就会涉及到完全背包问题，昨天的题目有一道叫做分割等和子集，今天应该会有与它思路相似的题目，那么我们就一起走进今天的题目。

第一题对应力扣编号为1049的题目最后一块石头的重量

         首先我们就直接看到这一道题目，看看我们是否可以发现究竟在考查哪一个算法：

       我们来看一下题意，就是我们有一堆石头，我们每一次可以选出任意两块石头并将其一起粉碎，如果两块石头的重量相同那么两块石头都会被完全粉碎，如果一块石头重量大一块石头重量小的话，那么我们重量小的石头会被完全粉碎，大的石头剩下的重量是大的石头减去小的石头，最后我们只会剩下一块石头，那么题目要求我们返回此石头的最小的可能重量，如果没有剩余就返回0，那么我们应该如何思考这一道题目呢？其实大家可以思考一下我们这一道题目如果我们从整体来思考的话，我们如果想让最后剩下的石头的重量最小甚至是0的话，我们是不是就需要看看我们的总重量是不是可以凑出两个总重量的一半，如果可以的话其实最后剩下的可能重量不就是0了，大不了我们把所有的石头绑起来一粉碎剩下的重量就是0了，那如果无法凑出呢？我们尽量让我们凑出的两个和的差值尽可能小，最后我们剩下的重量就是sum - 2 * dp[target], 这个target就是sum的一半，那这道题目与上一道分割等和子集其实就很相似了，我们都是看看能不能凑出和相等的两个子数组，那我们可以写出如下的代码：

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//表示在剩余容量可以装下的石头的重量vector<int> dp(1501, 0);int sum = 0;for (int i = 0; i < stones.size(); ++i) sum += stones[i];int target = sum / 2;//0-1背包的模板往上套就可以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];}
};

      最后dp[target]里是容量为target的背包所能背的最大重量。

      那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。最后的差值就是剩余石头的最小价值。大家有可能很好奇为什么不加绝对值，我哪里知道我分成的两堆石头那一边重量大，很明显只要凑不出一半就一定小，因此肯定是sum - dp[target]大，两个的差就是结果。这就是我们这一道题目的解题思路。

第二题对应力扣编号为494的题目目标和

          目标和这个题目的名字就像是背包问题又是看看能不能凑出某个数，我们还是来看一下具体的题目要求：

       我们来看一下题目要求，题目这个其实是我们可以将一个非负整数数组里面的所有整数随时添加正负号，最后看我们最后和是否可以等于我们的target,其实就是看看我们随时变换正负号是否能凑出我们的目标数，最后我们要返回所有的可行方案和，那我们应该可以看出来这道题应该还是背包问题，而且是一个0-1背包问题，那我们的思路应该是什么，首先我们要排除几种根本不可能凑出的情况，第一种就是我们的target的绝对值大于了我们数组的和这就不可能凑出来了就算我们的数组元素全正全负这两种极端情况也是凑不出来的，还有一种情况可能不太容易想到，我们假设加法的总和为x，那么减法对应的总和就是sum - x，其实题目就是要求我们求x - (sum - x) = target的方案数，我们可以解出x = (sum + target) / 2, 这是加法对应的和的表达式，那么其实就是背包问题了，我们是否可以装满背包容量为x的背包，使用我们原先数组的数，这就是题目转化，其实我们如果不转化的话是很难看出这道题目的背包思想究竟隐藏在哪里，例如sum是5，target是2 的话其实就是无解的，因此我们就可以得到第二种不可能凑出的情况就是sum + target是奇数，那么我们无论如何也凑不出来，接下来就是我们的背包思想了，其实就是看我们的方案总数，那么我们的dp数组表示的含义就得改改了，dp[j]，表示：填满j（包括j）这么大容积的包，有dp[j]种方法，最后我们返回的应该是dp[(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 (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) 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 - nums[i]];}}return dp[bagSize];}
}; 

       但是本题目如果上来就用一维dp的话其实很难，所以这里我打算给大家讲解二维dp的解法，我们知道背包二维dp的话我们先遍历物品还是先遍历背包都是可以的，

       首先确定二维数组的含义dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。 这个与我们以前的背包问题的含义的确存在一些不一样的地方，那么接下来一个很重要的事情就是我们要推导递推公式，这个挺难的，也不容易理解，大家看代码随想录给出我们只考虑物品0的情况：

       这个应该不难理解，注意我们的数组是表示的方法数，后面我们再考虑物品0和物品1都是一样的思路，所以我们举一个例子dp[2][2]表示的是我们放物品2的方法数与不放物品2的方法数，所以

dp[2][2] = dp[1][1] + dp[1][2],其实我们的递推公式大致就可以写出来了，dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]; 这个递推公式很重要以后还是会用到，dp数组如何初始化 ，这个问题也需要仔细考虑一下，我们既然要状态转移，那么我们就需要初始化最上面的一行与最左边的一行，

        关于dp[0][0]的值，装满背包容量为0 的方法数量是1，即 放0件物品。dp[0][j]：只放物品0， 把容量为j的背包填满有几种方法 ，只有背包容量为 物品0 的容量的时候，方法为1，正好装满。 其他情况下，要不是装不满，要不是装不下。dp[0][nums[0]] = 1 ，其他均为0 。还有dp[i][0] : 背包容量为0， 放物品0 到 物品i，装满有几种方法。其实很简单都是只有一种方法就是放0件物品，但这里有例外，就是如果 物品数值就是0呢？如果有两个物品，物品0为0， 物品1为0，装满背包容量为0的方法有几种。其实就是放物品0，放物品1，放物品0和物品1，放0件物品，所以我们可以得出其实就是算数组里有t个0，然后按照组合数量求，即 2^t 。这样关于遍历顺序我们还是选择先遍历物品再遍历背包就可以，我们在这里给出代码：

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 (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));// 初始化最上行if (nums[0] <= bagSize) dp[0][nums[0]] = 1; // 初始化最左列，最左列其他数值在递推公式中就完成了赋值dp[0][0] = 1; int numZero = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(2.0, numZero);}// 以下遍历顺序行列可以颠倒for (int i = 1; i < nums.size(); i++) { // 行，遍历物品for (int j = 0; j <= bagSize; j++) { // 列，遍历背包if (nums[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];}}return dp[nums.size() - 1][bagSize];}
};

       这道题的确有难度，大家一定要仔细静下心来好好思考一番。

第三题对应力扣编号为474的题目一和零

         这是我们今天的最后一道题目我们来看一下这道题目是什么意思：

        题目意思其实并不难，就是给我们一个二进制的字符串数组，给出我们两个数字m, n, 其实要求我们要找的子集里包含m个0和n个1，然后我们返回最大的子集的长度，这题目有意思，我们一起来看一下解题思路：这道题目应该还是得用背包问题解决，但是这是一个什么背包呀，怎么会是多重背包呢，我们这里的m,n可不是物品，如果是看成多重背包的应该是搞混了，这其实大家可以理解为这是背包的两个维度，我明确告诉大家本道题目依旧是0-1背包，只不过我们的背包维度是二维了，那我们就开始动规五部曲，第一步就是确定dp数组，dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。这个估计不难想到。

       确定递推公式估计有难度，我认为这也是题目的核心难点，我们思考一下，dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。因此dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。注意我们的dp数组表示的还是最大子集的长度，因此dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)，这就是递归公式，我认为很不好想，

     dp数组如何初始化这个与0-1背包的理论基础是一样的，还有遍历顺序本题物品就是strs里的字符串，背包容量就是题目描述中的m和n。那我们就给出解题代码：

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 oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; --i){for (int j = n; j >= oneNum; --j){dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};

      其实还是背包问题，我们依旧采用先物品再背包的遍历方式，当然要记得背包要倒序遍历。

今日总结

       目前来说我们讲的题目大多还是0-1背包，大家务必把0-1背包的理论基础理解扎实，而且要举一反三，我们能看出题目考的是背包问题，随后大家一定要注意dp数组是如何定义的，初始化的问题也要注意。今天我们就到这里，我们明天见！