代码随想录44——动态规划：完全背包理论基础、518零钱兑换II、377组合总和IV

1.完全背包理论基础

参考：代码随想录，完全背包理论基础

01背包和完全背包唯一不同就是体现在遍历顺序上，所以本文就不去做动规五部曲了，我们直接针对遍历顺序进行分析！

首先在回顾一下01背包的核心代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5
6

dp状态图如下：

其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？

这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？

难道就不能遍历背包容量在外层，遍历物品在内层？

看过这两篇的话：

动态规划：关于01背包问题，你该了解这些！
动态规划：关于01背包问题，你该了解这些！（滚动数组）

就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

遍历物品在外层循环，遍历背包容量在内层循环，状态如图：

遍历背包容量在外层循环，遍历物品在内层循环，状态如图：

看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）。

最后给出完全背包的测试代码（使用先遍历物品的方式）：

/**
 * @brief 使用一维dp数组测试完全背包
 * 
 */
void BagComplete()
{
    vector<int> weight = {1, 3, 4};    // 物品的重量
    vector<int> value = {15, 20, 30};  // 物品的价值
    int bag_weight = 4;   // 背包的容量 
    
    // 初始化dp数组全为0，注意其中列数是bag_weight+1，因为还包括0
    vector<int> dp(bag_weight+1, 0);  
    
    // 遍历dp数组，使用递推数组解决背包问题
    for(int i = 0; i < weight.size(); ++i)
    {
        // 完全背包，从前向后遍历
        for(int j = weight[i]; j <= bag_weight; j++)
        {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    
    cout << "result = " << dp[bag_weight] << endl;
    return;
}
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

注意：上面的讲解感觉没有讲清楚到底为什么完全背包需要从前往后遍历一维dp数组，这里推荐去看B站这个视频的讲解。其中最后总结01背包和完全背包的不同指出如下图所示：可以清楚的看到，二者的在二维dp数组中的递推公式中，红色部分是不一样的，01背包是使用0到i-1的物品的最大值，而完全背包是使用0到i的物品的最大值。但是如果化成一维dp数组，他们的递推公式就变成完全相同的了。其实不同指出就在于遍历顺序上：

• 由于01背包用的是上一行的dp数组，也就是dp[i-1][j-w[i]]，所以要从后往前遍历一维dp数组，这样保证遍历当前位置的时候，前面的dp数组没有被覆盖，从而保证我们使用的仍然是上一行的dp数组中值。
• 由于完全背包用的是当前行的dp数组，也就是dp[i][j-w[i]]，所以要从前往后遍历一维dp数组，这样保证遍历到当前位置的时候，前面的dp数组都已经被更新过了。
  

2.518零钱兑换II

参考：代码随想录，518零钱兑换II；力扣题目链接

2.1.题目

2.2.解答

这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包。

但本题和纯完全背包不一样，纯完全背包是能否凑成总金额，而本题是要求凑成总金额的个数！

注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？

例如示例一：

5 = 2 + 2 + 1

5 = 2 + 1 + 2
1
2
3

这是一种组合，都是 2 2 1。如果问的是排列数，那么上面就是两种排列了。组合不强调元素之间的顺序，排列强调元素之间的顺序。 其实这一点我们在讲解回溯算法专题的时候就讲过了哈。

这和下文讲解遍历顺序息息相关！

动规五部曲：

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

dp[j]：凑成总金额j的货币组合数为dp[j]

2.确定递推公式

dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。

所以递推公式：dp[j] += dp[j - coins[i]];

这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在 动态规划：目标和 中就讲解了，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];

注意：这里再次理解如何求组合数，遍历到当前的物品的时候，可以选择取还是不取：

• 如果不取当前的物品，那么最多的组合数就是从0到i-1的物品中填满容量为j的背包的最大组合数；
  注意：这里是从0到i-1，因为已经确定了我们当前不取这个物品i了，所以之前的操作就是从0到i-1中寻找填满容量为j的背包的最大组合数。
• 如果取当前的物品，那么最多的组合数就变成从0到i的物品中填满容量为j - w[i]的背包的最大组合数。注意：这里是从0到i，而不是从0到i-1，因为这里是完全背包问题，所以当前我取了这个物品i，那么之前的容量为j-w[i]的背包一样可以取物品i，所以是从0到物品i中取。

3.dp数组如何初始化

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]。

注意：这里的解释也是有一点不好理解，实际上还是可以跟昨天 494目标和 的那道题目一样，可以加入一个面值为0的硬币，所以背包容量为0的时候就只有一种组合就是加入一个0；背包容量为1/2/3等值的时候无法组合成功，所以组合个数就是0。因此初始化一维的dp数组为dp[0]=1，其他都是dp为0。

4.确定遍历顺序

本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）；还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？

之前讲解了完全背包的两个for循环的先后顺序都是可以的。但本题就不行了！

因为纯完全背包求得是能否凑成总和，和凑成总和的元素有没有顺序无关，即：有顺序也行，没有顺序也行！

而本题要求凑成总和的组合数，元素之间要求没有顺序。所以纯完全背包是能凑成总和就行，不用管怎么凑的。本题是求凑出来的方案个数，且每个方案个数是为组合数。

那么本题，两个for循环的先后顺序可就有说法了。

我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。

代码如下：

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}
1
2
3
4
5

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数！

如果把两个for交换顺序，代码如下：

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}
1
2
3
4
5

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数！

可能这里很多同学还不是很理解，建议动手把这两种方案的dp数组数值变化打印出来，对比看一看！（实践出真知）

5.举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：

最后给出代码如下：

int change(int amount, vector<int> &coins)
{
    vector<int> dp(amount+1, 0);
    dp[0] = 1;

    for(int i = 0; i < coins.size(); i++)
    {
        for(int j = coins[i]; j <= amount; j++)
        {
            dp[j] += dp[j-coins[i]];
        }
    }

    return dp[amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意：这道题目也没有特别理解，gg了，感觉背包问题开始有点理解不了了。。。。

3.377组合总和IV

参考：代码随想录，377组合总和IV；力扣题目链接

3.1.题目

3.2.解答

本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！

组合不强调顺序，(1,5)和(5,1)是同一个组合。排列强调顺序，(1,5)和(5,1)是两个不同的排列。

大家在公众号里学习回溯算法专题的时候，一定做过这两道题目回溯算法：39.组合总和和回溯算法：40.组合总和II会感觉这两题和本题很像！但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。如果本题要把排列都列出来的话，只能使用回溯算法爆搜。

动规五部曲：

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

dp[i]: 凑成目标正整数为i的排列个数为dp[i]

2.确定递推公式

dp[i]（考虑nums[j]）可以由 dp[i - nums[j]]（不考虑nums[j]） 推导出来。

因为只要得到nums[j]，排列个数dp[i - nums[j]]，就是dp[i]的一部分。

在动态规划：494.目标和 和 动态规划：518.零钱兑换II中我们已经讲过了，求装满背包有几种方法，递推公式一般都是 dp[i] += dp[i - nums[j]]; 本题也一样。

3.dp数组如何初始化

因为递推公式 dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。

至于dp[0] = 1 有没有意义呢？

其实没有意义，所以我也不去强行解释它的意义了，因为题目中也说了：给定目标值是正整数！ 所以dp[0] = 1是没有意义的，仅仅是为了推导递推公式。

至于非0下标的dp[i]应该初始为多少呢？

初始化为0，这样才不会影响dp[i]累加所有的dp[i - nums[j]]。

4.确定遍历顺序

个数可以不限使用，说明这是一个完全背包。

得到的集合是排列，说明需要考虑元素之间的顺序。本题要求的是排列，那么这个for循环嵌套的顺序可以有说法了。

在动态规划：518.零钱兑换II中就已经讲过了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！

所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。

5.举例来推导dp数组

我们再来用示例中的例子推导一下：

最后直接给出代码如下：

int combinationSum4(vector<int> &nums, int target)
{
    vector<int> dp(target + 1, 0);
    dp[0] = 1;   // 不要忘记初始化dp[0] = 1

    // 先遍历背包，再遍历元素，这样得到的是排列的问题
    for(int i = 0; i <= target; i++)
    {
        for(int j = 0; j < nums.size(); j++)
        {
            // 疑问：后面判断dp[i] < INT32_MAX - dp[i-nums[j]]是为什么？
            if(i - nums[j] >= 0 && dp[i] < INT32_MAX - dp[i-nums[j]])
                dp[i] += dp[i-nums[j]];
        }
    }

    return dp[target];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

疑问：这里也开始有点看不懂了。。。。

4.组合和排列问题的便利顺序

上面两道题目确实比较难理解了，如果画成二维的dp数组，或许还能看出来一些门道。

4.1.组合问题

对于组合问题，先遍历物品，再遍历背包，以518零钱兑换的题目为例，其二维dp数组如下：

可以看到，每个位置的组合数包括两部分：

• 如果取当前的这个数，则组合数是dp[i][j-nums[i]]，也就是把背包容量变成j-nums[i]，然后在0到i的物品中填满这个容量的背包的所有的组合数
• 如果不取当前的这个数，则组合数就是dp[i-1][j]，也就是背包容量仍然是j不变，然后在0到i-1的物品中填满这个容量的背包的所有的组合数

4.2.排列问题

对于排列问题，二维dp数组如下：

可以看到，每个位置的组合数包括两部分：

• 如果取当前的这个数，则组合数是dp[nums.size()][j-nums[i]]，也就是把背包容量变成j-nums[i]，然后在所有物品中填满这个容量的背包的所有的组合数，也就是找缩小之后的背包容量，然后对应的那一列的最下面值，也就是考虑了所有物品之后的最大组合数；
• 如果不取当前的这个数，则组合数就是dp[i-1][j]，也就是背包容量仍然是j不变，然后在0到i-1的物品中填满这个容量的背包的所有的组合数