代码随想录43——动态规划：1049最后一块石头的重量II、494目标和、474一和零

1.1049最后一块石头的重量II

参考：代码随想录，1049最后一块石头的重量II；力扣题目链接

1.1.题目

1.2.解答

1.2.1.思路

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

是不是感觉和昨天讲解的416. 分割等和子集非常像了。

本题物品的重量为stones[i]，物品的价值也为stones[i]。

对应着01背包里的物品重量weight[i]和 物品价值value[i]。

1.2.2.动规五部曲

这里的动规五部曲和划分等和的题目基本上是一样的：

• 首先计算石头的总重量，然后/2得到石头一半的重量
• 然后把这个重量当做背包的容量，并且石头的重量和价值都等于石头的重量
• 这样使用背包问题查找一半重量的容积的背包可以装的最大价值，这个最大价值肯定是 <= 背包的总容量的

和分割总和不同的是，我们要计算的另一堆的总价值就是sum - dp[target]，并且由于前面计算背包容量的时候使用的是/2向下取整，所以另一对的背包容量一定是>= target的，因此就可以得到另一堆的总价值肯定更是>= dp[target]的，所以最后两堆石头的价值差值就是sum - dp[target] - dp[target]。

直接给出代码，和昨天的代码非常相似：

int lastStoneWeightII(vector<int> &stones)
{
    // 1.计算石头的重量总和，/2得到背包容量，并以此初始化dp数组
    int sum = 0;
    for(const auto& num : stones)
        sum += num;
    int target = sum / 2;
    vector<int> dp(target+1, 0);

    // 2.遍历石头，使用01背包解决
    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]);
        }
    }

    // 最后返回两堆石头的重量差：sum-dp[target]是重量大的那堆石头，dp[target]是重量小的那堆石头
    return (sum - dp[target] - dp[target]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.494目标和

参考：代码随想录，494目标和；力扣题目链接

2.1.题目

2.2.解答

2.2.1.回溯算法暴力搜索

如果跟着「代码随想录」一起学过回溯算法系列的录友，看到这道题，应该有一种直觉，就是感觉好像回溯法可以爆搜出来。

事实确实如此，下面我也会给出相应的代码，只不过会超时，哈哈。

这道题目咋眼一看和动态规划背包啥的也没啥关系。

本题要如何使表达式结果为target，既然为target，那么就一定有 left组合 - right组合 = target。

left + right = sum，而sum是固定的。

公式来了： left - (sum - left) = target -> left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

2.2.2.动态规划算法

假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = S，x = (S + sum) / 2

此时问题就转化为，装满容量为x背包，有几种方法。

大家看到(S + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了，例如sum是5，S是2的话其实就是无解的，所以：

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

同时如果 S的绝对值已经大于sum，那么也是没有方案的。

if (abs(S) > sum) return 0; // 此时没有方案
1

再回归到01背包问题，为什么是01背包呢？

因为每个物品（题目中的1）只用一次！这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题了。

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

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

其实也可以使用二维dp数组来求解本题，dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

下面我都是统一使用一维数组进行讲解， 二维降为一维（滚动数组），其实就是上一层拷贝下来。

2.确定递推公式

有哪些来源可以推出dp[j]呢？

• 不考虑nums[i]的情况下，填满容量为j的背包，有dp[j]种方法。注意：这个dp[j]是上一行的dp[j]，也就相当于二维的dp数组中的dp[i-1][j]。

• 那么考虑nums[i]的话（只要搞到nums[i]），凑成dp[j]就有dp[j - nums[i]] 种方法。注意：这个dp[j - nums[i]也是上一行的，也就相当于二维dp数组的dp[i-1][j-nums[i]]。

例如：dp[j]，j 为5：

已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]
1
2
3
4
5

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]
// 写成如下形式更好理解
dp[j] = dp[j] + dp[j - nums[i]]
1
2
3

理解：使用二维的dp数组来看上面推出dp[j]的方法

• 求最大值的01背包：dp[i][j]中存储的是当前容量的背包所拿的物品的最大价值。如果不加入当前的元素nums[i]的话，其价值就是使用前面0到i-1的所有元素放入容量为j的背包中得到的最大价值，即dp[i-1][j]；如果加入当前的元素nums[i] 的话，其价值就是当前的元素的价值value[i]再加上使用前面0到i-1的所有元素放入容量为j-nums[i]的背包（注意这里元素的重量和价值都是nums[i]）得到的总价值，即dp[i-1][j-nums[i]] + nums[i]。那么由于背包是为了让最后的价值最大化，所以递推公式为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]。
• 求所有可能的组合的01背包：dp[i][j]中存储的是使用0到i的所有元素，正好放满容量为j的背包的所有可能的组合的个数。如果不加入当前的元素nums[i]的话，则就相当于仍然使用0到i-1的所有元素正好放满容量为j的背包得到的所有可能的组合的个数，即仍然是nums[i][j-1]；如果加入当前元素nums[i]的话，那么可能的组合个数就是使用前面0到i-1的所有元素放满容量为j - nums[i]的背包得到的所有的可能的组合的个数（注意这里面和放入nums[i]是没有关系的，因为放入他就是确定的，组合方案的个数是由剩下的背包的容量来确定的，这和前面放入他会产生一定的价值是不同的），也就是dp[i-1][j-nums[i]]。由于我们求的是方案的总数，所以递推公式是dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]。
  注意：从这个二维的dp递推公式可以发现，当前行的结果仍然是只依赖于上一行的左上角或者上一行的正上方的值，因此仍然可以把二维的dp数组压缩成一维，并且再遍历的时候内层循环必须从后往前遍历，这样才能复用上一层的结果。另外一个不同的地方在于，递推公式变成了加和，而不是max求最大值。因此变成一维的dp递推公式的时候，应该写成dp[j] = dp[j] + dp[j-nums[i]]，其实一维的dp递推公式就是把二维的dp递推公式中i的索引项给去掉。

3.dp数组如何初始化

从递归公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递归结果将都是0。dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。

dp[j]其他下标对应的数值应该初始化为0，从递归公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来。

注意：

其实上面解释的比较牵强，因为上面的解法是直接从给的数字开始的，比如给的数字如下图是1,1,1,1,1，也就是5个1，那么就从第一个1开始。实际上，按照下图画的方法，在最前面加一个0是更好的做法，这样有助于理解。

如果按照下图手动在给的数字最前面加一个0的话，那么初始化的dp数组就是第0行的dp数组，对他的解释的此时只有一个0，并且只能用一次，也就是要么用要么不用（01背包问题），问有多少中组合可以组成背包容量为j的背包？显然背包容量为0的时候，只有放入一个0这一种组合方式，所以dp[0] = 1；后面的话，由于容量都是大于0的，所以无论如何都是无法装满这些背包的，因此dp的值都是0。

然后按照下图，画成二维的dp数组之后就可以利用递推公式来看当前层的dp数组的值如何得到了，其实就是上一层的dp数组的左边和正上方的dp数组的和，如下面三个箭头所示。这样看起来就非常好理解了。

4.确定遍历顺序

在动态规划：我们讲过对于01背包问题一维dp的遍历，nums放在外循环，target在内循环，且内循环倒序。

5.举例推导dp数组

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

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

dp数组状态变化如下：

最后给出代码如下：

int findTargetSumWays(vector<int> &nums, int target)
{
    int sum = 0;
    for(const auto& num : nums)
        sum += num;
    // nums都是正数，所以sum一定>0，如果target过大或者过小，则一定不能组成结果
    if(abs(target) > sum)
        return 0;
    // 求left，如果left不能整除求出来，那么肯定也没有符合条件的结果
    if((sum + target) % 2)
        return 0;
    
    // 一切正常，求要寻找的和为left的数组
    int bag_size = (sum + target) / 2;
    vector<int> dp(bag_size+1, 0);
    dp[0] = 1;  // dp[0]初始化成1，其他全都初始化成0
    
    for(int i = 0; i < nums.size(); i++)
    {
        for(int j = bag_size; j >= nums[i]; j--)
        {
            // 重要：累加总和的不同组合个数
            dp[j] += dp[j - nums[i]];
		  // 写成如下形式更好理解：
		  dp[j] = dp[j] + dp[j-nums[i]];
        }
    }
    
    // 最后返回left总和组合的结果个数
    return dp[bag_size];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

另外，如果使用二维dp数组来求解上面的题目，代码如下，经过测试也是可以AC的。其过程和上面自己写的理解中画的dp数组的图是一样的，这里使用在给定的数字中最前面添加一个0来实现：

// 使用二维dp数组求解
int findTargetSumWays(vector<int> &nums, int target)
{
    int sum = 0;
    for(const auto& num : nums)
        sum += num;
    // nums都是正数，所以sum一定>0，如果target过大或者过小，则一定不能组成结果
    if(abs(target) > sum)
        return 0;
    // 求left，如果left不能整除求出来，那么肯定也没有符合条件的结果
    if((sum + target) % 2)
        return 0;
    
    // 一切正常，求要寻找的和为left的数组
    int bag_size = (sum + target) / 2;
    // 使用二维dp数组的形式，注意在最前面添加元素0，所以dp数组的行数是nums.size()+1
    vector<vector<int>> dp(nums.size()+1, vector<int>(bag_size+1, 0)); 
    // 初始化添加的第0行的dp数组的值，只有dp[0][0]=1，其他仍然维持0不变
    dp[0][0] = 1;  
    
    // 从nums的元素开始遍历，因为dp数组的第0行已经初始化完了
    for(int i = 1; i <= nums.size(); i++)
    {
        // 从前往后还是从后往前遍历都无所谓了，因为我们用的是二维的dp数组
        for(int j = 0; j <= bag_size; j++)
        {
            // 注意这里小心数组越界：i是dp数组的索引，而i-1才是nums数组的索引
            if(j < nums[i-1])   // 背包容量 < 元素的值，放不下这个元素
                dp[i][j] = dp[i-1][j];  // 则组合数就等于上一个组合数
            else  // 能放下这个元素，可以选择放或者不放，所以最后组合数是相加
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
        }
    }
    
    // 最后返回left总和组合的结果个数
    return dp[nums.size()][bag_size];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

3.474一和零

参考：代码随想录，474一和零；力扣题目链接

3.1.题目

3.2.解答

注意这道题目不是多重背包，因为多重背包是每个物品数量不同的情况，而本题中strs数组里的元素就是物品，每个物品都是一个，而m和n则是相当于一个背包的两个维度，也就是加入背包的中的元素需要同时满足这个两个维度的容量的限制！

理解成多重背包的同学主要是把m和n混淆为物品了，感觉这是不同数量的物品，所以以为是多重背包。但本题其实是01背包问题！这不过这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。

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

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

2.确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就有两个方式可以推导出来：

• 如果加入当前的字符串，那么集合中字符串的最大个数就是dp[i - zeroNum][j - oneNum] + 1。注意：这个+1表示把当前字符串加到集合中，因此多了一个字符串。而dp[i - zeroNum][j - oneNum]表示由于加入当前字符串之后0和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背包！ 只不过物品的重量有了两个维度而已。

3.dp数组如何初始化

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

注意：其实这道题目如果从二维dp数组的角度来看，dp数组就要变成dp[i][j][k]的这种形式了，其中i表示遍历所有的字符串，也就是物品；j/k两个维度分别表示的是背包中0/1的个数，这是一个有两个维度的容量的背包，所以最后如果从二维dp数组的角度来看，把dp数组画出来的话实际上是一个三维的立方体！

那么再来思考dp数组初始化成0代表什么呢？跟前面一样，我们在给定的字符串集合的最前方加入一个空的位置，它表示这个位置是空，加入背包中不会造成背包的0/1容量的损失，也不会增加背包中字符串的个数，所以他就相当于一个纯粹的占位符号。

然后后面遍历到第i个字符串的时候，我们就可以根据递推公式来计算在当前背包容量下，是加入这个字符串得到的字符串个数最多，还是不加入这个字符串得到的字符串个数最多？如果不加入这个字符串，那么我们得到的字符串的个数就是在背包容量为j/k的时候，从前面的第0到第i-1个字符串中加入背包，得到的最多的字符串的个数，即dp[i-1][j][k]；如果加入这个字符串，那么首先字符串的个数+1（这个地方就对应01背包中的+value[i]），然后背包的容量减小，从j/k 变成j-zeroNum/k-oneNum，所以另一部分就是从第0到第i-1的字符串中加入背包容量为j-zeroNum/k-oneNum的背包得到的最多的字符串的个数，所以最终如果加入当前第i个字符串的话，得到的背包中最大的字符串的个数为dp[i-1][j-zeroNum][k-oneNum] + 1。

4.确定遍历顺序

一定是外层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);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

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

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

5.举例推导dp数组

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

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

注意：下图是递推最后的dp数组，前面自己的讲解中说了，实际如果看二维的dp数组的话，最后画出来是一个立方体，也就是遍历到每一个字符串的时候，都会有如下图的一个dp数组，因为这里的背包有两个维度。

最后给出整体代码如下：

// 一维dp数组的解法，这里背包有两个维度j/k，所以压缩后的一维dp数组的形式是dp[j][k]
int findMaxForm(vector<string> &strs, int m, int n)
{
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    // 遍历所有的字符串
    for(const auto& str : strs)
    {
        // 首先计算这个字符串中0/1字符的个数，这个就相当于这个物品的两个维度的重量
        int zero = 0;
        int one = 0;
        for(const auto& c : str)
        {
            if(c == '0')
                zero++;
            else
                one++;
        }

        // 然后遍历背包的两个维度，判断是否要加入这个字符串，看如何才能让字符串的个数最多
        for(int i = m; i >= zero; i--)  
        {
            for(int j = n; j >= one; j--)
            {
                dp[i][j] = max(dp[i][j], dp[i-zero][j-one] + 1);
            }
        }
    }

    // 最后for循环便利完所有字符串之后，就得到了最终最多的字符串的个数
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

如果使用二维dp数组，参考上一道题目，代码如下，经过测试也是可以AC的。其思路和上一道题目一样，其实本质上还是二维dp数组的01背包问题，只不过这里把背包扩展成了具有两个容量维度的背包，在放物品的过程中要同时考虑到两个容量的限制。

// 如果考虑二维dp数组的形式，那么应该在最前面加入物品的维度i，也就是dp[i][j][k]
int findMaxForm(vector<string> &strs, int m, int n)
{
    // 在最前面加入一个空的字符串，所以总的维度是strs.size()+1
    vector<vector<vector<int>>> dp(strs.size()+1, vector<vector<int>>(m+1, vector<int>(n+1, 0)));

    // 遍历所有的字符串
    for(int i = 1; i <= strs.size(); i++)
    {
        // 首先统计当前字符串中0/1的个数
        int zero = 0;
        int one = 0;
        for(const auto& c : strs[i-1])  // 注意dp数组索引是i，但是str的索引是i-1
        {
            if(c == '0')
                zero++;
            else
                one++;
        }

        // 从前往后遍历不同容量的背包，更新dp数组的值
        for(int j = 0; j <= m; j++)
        {
            for(int k = 0; k <= n; k++)
            {
                if(j < zero || k < one)  // 如果这个字符串的0/1个数超过了容量，则不加入
                    dp[i][j][k] = dp[i-1][j][k];
                else  // 否则可以加入，判断是加入得到的字符串个数多，还是不加入得到的字符串个数多，取最多的那个
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero][k-one] + 1);
            }
        }
    }

    return dp[strs.size()][m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35