动态规划 4️⃣

416. 分割等和子集

力扣题目链接

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

思路

这道题目初步看，和如下两题几乎是一样的，大家可以用回溯法，解决如下两题

698.划分为k个相等的子集
473.火柴拼正方形

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

本题是可以用回溯暴力搜索出所有答案的，但最后超时了，也不想再优化了，放弃回溯，直接上01背包吧。

01背包问题

背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。

要注意题目描述中商品是不是可以重复放入。

即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。

要明确本题中我们要使用的是01背包，因为元素我们只能用一次。

回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集。

那么来一一对应一下本题，看看背包问题如何来解决。

只有确定了如下四点，才能把01背包问题套到本题上来。

背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。

以上分析完，我们就可以套用01背包，来解决这个问题了。

动规五部曲分析如下：

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

01背包中，dp[j] 表示：容量为j的背包，所背的物品价值最大可以为dp[j]。

本题中每一个元素的数值既是重量，也是价值。

套到本题，dp[j]表示背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。

那么如果背包容量为target， dp[target]就是装满背包之后的重量，所以当 dp[target] == target 的时候，背包就装满了。

有录友可能想，那还有装不满的时候？

拿输入数组 [1, 5, 11, 5]，举例， dp[7] 只能等于 6，因为只能放进 1 和 5。

而dp[6] 就可以等于6了，放进1 和 5，那么dp[6] == 6，说明背包装满了。

确定递推公式

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

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

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

dp数组如何初始化

在01背包，一维dp如何初始化，已经讲过，

从dp[j]的定义来看，首先dp[0]一定是0。

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。

本题题目中只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

代码如下：

1
2
3

// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector<int> dp(10001, 0);

确定遍历顺序

在动态规划：关于01背包问题，你该了解这些！（滚动数组）中就已经说明：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

代码如下：

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}

举例推导dp数组

dp[j]的数值一定是小于等于j的。

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

用例1，输入[1,5,11,5] 为例，如图：

最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

综上分析完毕，C++代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        // 也可以使用库函数一步求和
        // int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        // 如果总和是奇数，直接返回 false
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        // 初始化 `dp` 数组，其中 `dp[0] = true` 表示可以得到和为 0 的子集。
        dp[0] = true;
				// 对于数组中的每个数字，更新 `dp` 数组。倒序遍历是为了防止重复计算。
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[target];
    }
};

总结

这道题目就是一道01背包应用类的题目，需要我们拆解题目，然后套入01背包的场景。

01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。

看代码的话，就可以发现，基本就是按照01背包的写法来的。

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

力扣题目链接

有一堆石头，每块石头的重量都是正整数。

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

如果 x == y，那么两块石头都会被完全粉碎；

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

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

示例：

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

解释：

组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

思路

该问题可以转换为“0/1背包问题”。我们需要找到一个方式把石头分成两堆，使得两堆的重量差最小。令总重量为 sum，我们要找到一个接近 sum/2 的重量 P，使得 |sum - 2P| 最小。

定义状态：dp[i] 表示可以通过选择部分石头，使得这些石头的总重量恰好为 i 的最大重量。

状态转移：遍历所有的石头，对于每个石头 stone，从后向前更新 dp 数组：dp[i] = max(dp[i], dp[i - stone] + stone)。这样可以确保每块石头只使用一次。

初始条件：dp[0] 初始化为 0，因为没有石头时，总重量为 0 是可以实现的。

最终结果：从总重量的一半 target 向下遍历，找到最大的 dp[target]，然后计算 sum - 2 * dp[target]，即为剩下的最小重量。

举例推导dp数组

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

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

那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。

在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

以上分析完毕，C++代码如下：

class Solution {
public:
  int lastStoneWeightII(vector<int>& stones) {
    // 求石头的总重量
    int sum = accumulate(stones.begin(), stones.end(), 0);
    // 目标重量，即总重量的一半
    int target = sum / 2;
    // 初始化dp数组，dp[i]表示能够达到重量i的最大重量
    vector<int> dp(target + 1, 0);

    // 遍历每块石头
    for (int stone : stones) {
      // 从后向前更新dp数组
      for (int i = target; i >= stone; i--) {
        dp[i] = max(dp[i], dp[i - stone] + stone);
      }
    }
    // 返回最终的结果，即最小的剩余石头重量
    return sum - 2 * dp[target];
  }
};

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

494.目标和

力扣题目链接

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

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

解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

提示：

数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。

思路

动态规划

为了更好地解决这个问题，我们可以将它转换成一个等价的背包问题。具体步骤如下：

定义两个子集：
- P：所有添加 + 的元素的子集
- N：所有添加 - 的元素的子集
则我们有：
1
sum(P) - sum(N) = S

求和转换：
我们也知道：

1	sum(P) + sum(N) = sum(nums)

将这两个等式相加：

1 2	sum(P) - sum(N) + sum(P) + sum(N) = S + sum(nums) 2 * sum(P) = S + sum(nums)

所以：

1	sum(P) = (S + sum(nums)) / 2

判断是否有解：
- 如果 S + sum(nums) 不是偶数，则没有解，因为 sum(P) 必须是整数。
- 如果 S > sum(nums)，也没有解，因为 P 中所有元素的和不可能超过 nums 的总和。

我们将问题转换为一个背包问题，即找到一个子集 P，使其和等于 (S + sum(nums)) / 2。

定义状态：
用一个一维数组 dp 表示在考虑前 i 个数时，组成和为 j 的子集数。dp[j] 表示和为 j 的子集数。
初始化：
- dp[0] = 1，表示和为 0 的子集有一种，即空集。
状态转移：
对于数组中的每一个数字，从后向前更新 dp 数组。这样可以避免重复使用同一个数字。

C++代码如下：

我们先计算数组的总和 sum，然后判断是否有解。如果有解，则使用动态规划来计算方法数。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        
        // 判断 (S + sum) 是否为偶数，并且 S + sum >= 0
        if ((S + sum) % 2 != 0 || S > sum) return 0;

        int target = (S + sum) / 2;
        
        // 定义 dp 数组
        vector<int> dp(target + 1, 0);
        dp[0] = 1; // 初始化 dp[0] = 1
        
        // 动态规划更新 dp 数组
        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                dp[j] += dp[j - num];
            }
        }
        
        return dp[target];
    }
};

时间复杂度：，n为正数个数，m为背包容量
空间复杂度：，m为背包容量

解释

初始化：dp[0] = 1，表示和为 0 的子集有一种，即空集。
遍历数组：对于每一个 num，从后向前更新 dp 数组：
- 如果我们从前向后更新，会导致一个数字被使用多次，因为当前更新的 dp[j] 会依赖已经更新过的 dp[j - num]。
- 从后向前更新可以确保每个数字只被使用一次。
返回结果：最终 dp[target] 即为目标和为 S 的方法数。

示例

假设 nums = [1, 1, 1, 1, 1]，S = 3。

总和 sum(nums) = 5。我们需要找到一个子集 P，使其和为 (3 + 5) / 2 = 4。

动态规划数组 dp 初始化为 [1, 0, 0, 0, 0]，然后按照上述步骤更新 dp 数组。

最终，dp[4] 的值为 5，表示有 5 种方法使得数组和为 3。

回溯法

回溯法的思想是通过递归遍历所有可能的符号组合，并计算每种组合的和是否等于目标值 S。

定义递归函数：递归函数需要两个参数，一个是当前索引 index，表示当前处理的数字，另一个是当前的和 currentSum。
递归终止条件：如果已经处理到数组的最后一个元素（即 index 等于数组长度），则检查当前和是否等于目标值 S，如果是，则记录一种有效组合。
递归处理：对于当前数字，有两种选择，分别在当前和 currentSum 上加上当前数字或减去当前数字。然后递归处理下一个数字。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int count = 0;
        backtrack(nums, S, 0, 0, count);
        return count;
    }

private:
    void backtrack(const vector<int>& nums, int S, int index, int currentSum, int& count) {
        // 递归终止条件
        if (index == nums.size()) {
            if (currentSum == S) {
                count++;
            }
            return;
        }

        // 选择加上当前数字
        backtrack(nums, S, index + 1, currentSum + nums[index], count);

        // 选择减去当前数字
        backtrack(nums, S, index + 1, currentSum - nums[index], count);
    }
};

递归函数定义：
- backtrack(nums, S, index, currentSum, count)：
  - nums：输入的数字数组。
  - S：目标和。
  - index：当前处理的数字索引。
  - currentSum：当前计算的和。
  - count：记录满足条件的组合数。
递归终止条件：
- 如果 index 达到 nums 的长度，检查 currentSum 是否等于 S，如果是，则 count 加 1。
递归处理：
- 先将当前数字加到 currentSum 上，并递归处理下一个数字。
- 再将当前数字减去，并递归处理下一个数字。

示例

假设 nums = [1, 1, 1, 1, 1]，S = 3。

初始调用 backtrack(nums, 3, 0, 0, count)。
递归树会遍历所有可能的加减组合，最终找到 5 种满足条件的组合，count 的值即为结果。

通过这种方法，我们可以遍历所有可能的组合，虽然回溯法的时间复杂度较高，但它简单直观，适合理解问题的解空间。

总结

在动态规划中，使用 max() 或相加取决于问题的性质和我们要解决的具体目标。具体来说，不同的动态规划问题会有不同的状态转移公式，选择使用 max() 或相加是根据我们需要在每一步中获取的信息来决定的。

背包问题 (max())

背包问题的目的是在给定容量的限制下，最大化（或最小化）背包中物品的总价值。因此我们需要在每一步选择最优解，这里使用 max()。

例如，在 0/1 背包问题中：

•	dp[j] 表示容量为 j 的背包能装的最大价值。
•	对于每个物品，我们决定是否放入背包。
•	状态转移方程为：

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

这里我们选择了 max()，因为我们希望每个状态 j 表示当前可以达到的最大价值。

目标和问题 (相加)

目标和问题是要计算有多少种方法可以达到目标值 S，这是一个计数问题。我们需要累加所有可能的情况，因此使用相加。

在目标和问题中：

•	dp[j] 表示和为 j 的不同方法数。
•	对于每个数 num，我们决定是否使用它。
•	状态转移方程为：

dp[j] = dp[j] + dp[j - num]

这里我们选择了相加，因为我们希望每个状态 j 表示可以达到和为 j 的所有不同方法数。

474.一和零

力扣题目链接

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

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

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

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

思路

本题其实是01背包问题！

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

而m 和 n相当于是一个背包，两个维度的背包。只不过这个背包有两个维度，一个是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]），字符串本身的个数相当于物品的价值（valu◊e[i]）。

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

dp数组如何初始化

01背包的dp数组初始化为0就可以。因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

确定遍历顺序

01背包一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n。

代码如下：

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

有同学可能想，那个遍历背包容量的两层for循环先后循序有没有什么讲究？

没讲究，都是物品重量的一个维度，先遍历哪个都行！

举例推导dp数组

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

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

以上动规五部曲分析完毕，C++代码如下：

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

时间复杂度: ，k 为strs的长度
空间复杂度:

总结

不少同学刷过这道题，可能没有总结这究竟是什么背包。

此时我们讲解了0-1背包的多种应用，

纯 0 - 1 背包是求给定背包容量装满背包的最大价值是多少。
416.分割等和子集是求给定背包容量，能不能装满这个背包。
49.最后一块石头的重量 II 是求给定背包容量，尽可能装，最多能装多少
494.目标和是求给定背包容量，装满背包有多少种方法。
本题是求给定背包容量，装满背包最多有多少个物品。

Channing's Blog

动态规划 4️⃣

416. 分割等和子集

思路

01背包问题

总结

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

思路

494.目标和

思路

动态规划

回溯法

总结

474.一和零

思路

总结