代码随想录算法训练营DAY43|C++动态规划Part5|1049.最后一块石头的重量II、494.目标和、474.一和零

文章目录

1049.最后一块石头的重量II
- 思路
- CPP代码
⭐️494.目标和
- 回溯算法
- 抽象成01背包问题
- CPP代码
- 本题总结
474.一和零
- 思路
- CPP代码

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

力扣题目链接

文章链接：1049.最后一块石头的重量II

视频链接：这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II

状态：想破脑袋想不出来怎么抽象成背包问题
看完思路之后的状态：也不用想破脑袋

把这些石头尽可能得分成两堆，如果这两堆石头重量相似的话，相撞之后所剩的值就是最小值。

思路

正如上文所说的思路，本题基本就能解出来了（这能想到？）

举例[2, 7, 4, 1, 8, 1]。所有石头重量之和为sum=23->sum/2=11，也就是说，每一堆的重量应该是11，显然我们能凑成11的石头堆([2, 8, 1])，另一堆是12，相撞之后为1；

如果是[31, 26, 33, 21, 40]，sum=151->sum/2=75，每堆石头重量最好是75（也就是背包容量）,然而，该例子我们对多也只能装[33, 40]为73，也就是装不满这个石头堆，另一堆就是78，相撞之后为5

现在能懂吗！现在本题就变得相当简单了。

现在我们重新定义本题：（拿stones=[31, 26, 33, 21, 40]举例）

背包的bagweight=sum/2，物品个数有5个，velue=[31, 26, 33, 21, 40]、weight=value=[31, 26, 33, 21, 40]

dp含义：

用一维dp数组dp[j]，其表示背包重量为j时，任选0-i的物品的最高价值。（这里看不懂推荐阅读文章：0-1背包理论基础之滚动数组（二）

递推公式：

dp[j]=max(dp[j], dp[j-weight[i]]+value[i])

初始化：

dp[j]中的j表示容量，那么最大容量（重量）是多少呢，之前提到过，就是所有石头重量和的一半。

也就是先遍历一遍石头，计算出石头总重量然后除以2，得到dp数组的大小。

当然了，为了尽可能提高效率，我们可以直接把dp数组开到题目所给范围的最大值。

提示中给出 $1 <= s t o n es . l e n g t h <= 30$ ， $1 <= s t o n es [i] <= 1000$ ，所以最大重量就是30 * 1000

所以dp数组开到15000大小就可以了。

vector<int> dp(15001, 0);

遍历顺序：

如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

打印：

举例，输入：[2,4,1,1]，此时target = (2 + 4 + 1 + 1)/2 = 4

后续处理
之前我们已经拿到过背包的最大容量了bagweight = sum / 2，等我们装满这个背包后，石头堆已经被我们分成了两部分，一部分已经被我们装进了背包里，为dp[bagweight]，另一部分就是sum - dp[bagweight]。
把这两堆石头的总容量对撞：

return (sum-dp[bagweight]) - dp[bagweight];

CPP代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
    	//计算石头堆一共有多重
        int sum = accumulate(stones.begin(), stones.end(), 0);
		
		//分成两半后，我们背包的最大容量
        int bagweight = sum / 2;
        vector<int> dp(bagweight + 1, 0);
		
		//开始装石头
        for (int i = 0; i < stones.size(); i++) {
            for (int j = bagweight; j >= stones[i]; --j) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
		
		//装完石头后就被分成两堆了
        return (sum - dp[bagweight]) - dp[bagweight];
    }
};

⭐️494.目标和

力扣题目链接

文章链接：494.目标和

视频链接：装满背包有多少种方法？| LeetCode：494.目标和

状态：本题很重要，几乎奠定了后面求背包问题之组合的相关问题。本题的问法是很不一样的，他要求的是一共有多少种装法。

回溯算法

其实很直接就能想到回溯算法，也就是把本题转变为组合总和问题，只不过确实会超时。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (S > sum) return 0; // 此时没有方案
        if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
        int bagSize = (S + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和

        // 以下为回溯法代码
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 需要排序
        backtracking(nums, bagSize, 0, 0);
        return result.size();
    }
};

抽象成01背包问题

还记得我们之前做过的1049.最后一块石头的重量II和416.分割等和子集都是将数组拆分成了两部分，那么本题是不是也可以拆分成两部分呢？

对于给定数组nums和整数target，既然题目要求在其中插入正负号，也就是说把数组分成了总和为left的数组和总和为right的数组，其中left-right=target。再一个，我们有left+right=sum；
$l e f t - r i g h t = t a r g e t$
$l e f t + r i g h t = s u m$

既然target和sum都是固定数值，可以推导出

$l e f t - (s u m - l e f t) = t a r g e t$
$l e f t = (t a r g e t + s u m) /2$

很明显，本题中我们就是在集合nums中找出和为left的组合，背包的容量为(target+sum)/2

既然出现了除法，那么我们就必须考虑向下取整对结果有没有影响。

首先如果(target+sum)/2不能被2整除，说明left作为背包容量竟然是一个小数才行！所以很明显本题是无解的；如果target的绝对值大于sum，本题也是无解的。

关于这一点，更具体得来说。
如果sum为nums中数字的和，我们将目标值和sum相加得到target+sum，该值表示所有数字添加正号后的总和，如果 target + sum 是奇数，说明无论怎样给数字添加正负号，它们的和都无法变成 target，因为无论怎样选择符号，最终的结果都会与 target + sum 的奇偶性相反。

if ((target + sum) % 2 == 1) return 0; // 此时没有方案
if (abs(target) > sum) return 0; // 此时没有方案

综上，我们可以安心把物品放入背包了！

确定dp数组以及下标含义：这里仍然使用一维dp数组，具体可以看文章0-1背包理论基础之滚动数组（二）。

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法（这里的最大背包容量为我们之前提到的(target+sum)/2

确定递推公式

本题跟之前不一样，之前都是求容量为j的背包，最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题了。

我们对dp[j]的定义即，填满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[j] += dp[j - nums[i]]

dp数组如何初始化

dp[0]肯定是要初始化为1的，表示不选择任何数字也是一种组合方式；再一个，如果把dp[0]初始化成0，那么后面所有结果都将变成0；我们也可以把dp[0]的情况带入本题看看是多少
然后我们dp[j]( $j > 0$ )，他依赖于前面的dp[j - nums[i]]，所以后面的全部要初始化为0

vector<int> dp(bagSize + 1, 0);
dp[0] = 1;

确定遍历顺序

在0-1背包理论基础之滚动数组（二）中，我们讲过对于01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。

推导dp数组

输入：nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下：

CPP代码

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];
    }
};
时间复杂度：O(n × m)，n为正数个数，m为背包容量
空间复杂度：O(m)，m为背包容量

本题总结

在求装满背包有几种方法的情况下，递推公式一般为：

dp[j] += dp[j - nums[i]];

474.一和零

力扣题目链接

文章链接：474.一和零

视频链接：装满这个背包最多用多少个物品？| LeetCode：474.一和零

状态：我觉得是01背包里最难想到的一个，但是很有意思！写的时候只知道可以用两个维度来解决。递推公式并没有退出来

题目中要求m个零，n个1；

我们把这俩理解成两个容器，那么装满这两个容器最多有多少个元素，就输出多少个。

再更进一步，我们是不是也能一个背包有两个维度，然后来装这些元素。

其中m用来装0，n用来装1，所以两个维度的最高容量分别是m和n

思路

动规五部曲：

确定dp数组以及下标的含义

本次的背包有两个维度，所以我们必须使用二维的dp数组

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

NOTE:
这里最值得关注的就是本题的dp数组中的两个维度，这两个维度应该理解成每一维都是一个背包，我们要同时满足两个背包

确定递推公式

我们当前的dp[i][j]可以由前一个strs里的字符串推导得来，也就是说对于某个字符串0001而言，有zeroNum=3个0，oneNum=1个1。

那么dp[i][j]应该是dp[i - zeroNum][j - oneNum] + 1。

所以递推公式总结如下：

dp[i][j]=max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)

NOTE:

01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

dp数组的初始化

01背包的dp数组初始化为0就可以。

因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

确定遍历顺序

在本题中物品就是strs里的字符串，背包容量是题目描述中的m和n分别代表了dp数组的两个维度

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);
        }
    }
}

举例推导dp数组

以输入：[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3为例

CPP代码

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 (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];
    }
};