day43 | 1049. 最后一块石头的重量 II、494. 目标和、474.一和零-Toy模板网

这篇具有很好参考价值的文章主要介绍了day43 | 1049. 最后一块石头的重量 II、494. 目标和、474.一和零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

解题及思路学习

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

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1

思考：要剩下的石头尽可能重量小，所以就是背包的重量尽可能接近总值的一半。

随想录：

1、dp[j] 表示背包容量为j的最大价值dp[j]. 本题中价值等于重量，所以也就是最大重量dp[j].

2、dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ⇒ dp[j] = max(dp[j], dp[j-stone[i]] + ston[i]);

3、初始化。dp[0] = 0, 非零下标初始化为0.

4、确定遍历顺序。第一层for循环遍历的是物品，第二层for循环遍历的是背包。为了保证所有物品只放了一次，所以是从大到小去遍历。（如果从小大遍历就是完全背包了）

5、举例推导dp数组

举例，输入：[2,4,1,1]，此时target = (2 + 4 + 1 + 1)/2 = 4 ，dp数组状态图如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2apHXva6-1688570040937)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/b43630c5-e46b-43c0-b83f-c12a514651db/Untitled.png)]

代码：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[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 - dp[target] - dp[target];
    }
};

时间复杂度：O(m × n) , m是石头总重量（准确的说是总重量的一半），n为石头块数
空间复杂度：O(m)

这道题dp的定义很关键，是容量为j的时候，所能装的最大价值（重量）。注意容量不一定都要用完j。

494. 目标和

https://leetcode.cn/problems/target-sum/

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5

思考：思不开，想不到。

随想录：nums里面的数组可以分为正数类集合（left) 和负数类集合 (right) 。那么有→

left + right = sum , left - right = target. ⇒ left = (sum + target) /2;

当 (sum + target) 不能整除2的时候，说明不满足条件，返回0。再dp过程中要尽量能够是正数这个集合（背包）装满。本题相当于是给我们一个背包容量，有多少种方式能把背包装满。此时问题就转化为，装满容量为x的背包，有几种方法。

这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了。

1、dp[j] 装满背包容量为j ，有dp[j]种方法。

2、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]] 累加起来。

3、dp[0] = 1; 非零下标初始化为0.

4、遍历顺序。第一层遍历物品，第二层遍历背包。倒序。

5、举例推导dp数组

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

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Le1tJjWa-1688570040941)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/2fae4be7-6fe7-4f58-a02f-21ede6495323/Untitled.png)]

代码：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + 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为背包容量

个人感觉上面的递推公式那里有一定的误导性。几个nums[i] 会让人觉得只跟nums[i] 的个数有关，但其实是和nums[i]中的数值有关。如果例如nums[i] 是2的话，那么dp[j] += dp[j-2] 。给的例子中只是因为都是1这种巧合。所以应该是：背包容量已经有了2的话，那么剩下j-2 容量，所以是dp[j-2]种填满方法。

474.一和零

https://leetcode.cn/problems/ones-and-zeroes/

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4

思考：最大子集，感觉是要填两个背包m和n。填这两个背包种记录一个最大子集长度。

随想录：要装满m和0，n个1这么大容器的背包，这个背包里面最多有多少个物品。

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

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

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[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。
dp数组如何初始化

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

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

外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
举例推导数组

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

最后dp数组的状态如下所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vSq8a5GR-1688570040943)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c563df54-a1a7-49bf-a001-3f6555d9eef8/Untitled.png)]

代码：

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

时间复杂度: O(kmn)，k 为strs的长度
空间复杂度: O(mn)