动态规划(一) —— 从背包系列问题看DP_背包dp

前言

        动态规划可以算是算法初学者的噩梦哈哈，这段时间荔枝在持续学习Java后端的同时也没有忘记刷题嘿嘿嘿，总算把代码随想录上给出的有关动态规划的题目刷完了。接下来的几篇文章荔枝将会对于刷过的动态规划问题做出总结并给出相应的个人体会和理解。在本篇文章中荔枝首先来总结一下动态规划中的背包问题，主要包括：0-1背包问题、完全背包问题和多重背包问题，希望能给正在学习的小伙伴们带来一些帮助~~~

---

文章目录

前言

一、背包问题

二、0-1背包问题

2.1 dp数组的定义及其推导式

2.1.1 二维数组

2.1.2 滚动数组

2.2 0-1背包的经典例题

2.2.1 Leecode416.分割等和子集

2.2.2 Leecode494.目标和

2.2.3 Leecode474.一和零

三、完全背包问题

3.1 两种遍历顺序示例 

3.2 完全背包问题典例

3.2.1 Leecode518.零钱兑换||

3.2.2 Leecode组合总和IV

3.2.3 Leecode70.爬楼梯 

3.2.4 Leecode322.零钱兑换

3.2.5 Leecode139.单词拆分

四、多重背包问题

总结

---

一、背包问题

        背包问题，顾名思义就是拿背包来装物品，物品的数量可以是一个也可以是无数个，物品的种类可以是一种也可以是多种。背包有一个具体的最大容量v，而每一个物品都有其对应的价值value和体积weight，题目常常要求我们求出背包能装下物品的最大价值或者求解装满这个背包一共有多少种方法。其实很多动态规划的问题都可以转化成求解背包问题，因此学好背包问题尤为重要。在面试中常考的背包问题主要有三类：0-1背包问题、完全背包问题和多重背包问题，具体题目要求区别如下：

• 0-1背包问题：给定物品的价值数组和体积数组，并且所有种类物品的数量只有一个
• 完全背包问题：给定物品的价值数组和体积数组，所有种类的物品数量不限
• 多重背包问题：给定物品的价值数组和体积数组，不同种类的物品数量也不相同

从上面为我们可以看出其实这三种背包问题最大的区别就是在于物品的种类和数量上的差异，不同的条件对于我们dp递推公式的推导和遍历顺序都是不一样的。很多题目最难的就是确定dp数组的含义，dp推导式如何推导以及初始化的值如何设定，这些我们需要拿一些题目来体会一下这个确定的过程。

---

二、0-1背包问题

        首先我们来看看0-1背包问题，在前面荔枝已经写出三种背包问题的区别——物品的数量和种类。标准的0-1背包问题是这么描述的：有n件物品和一个最多能背重量为w的背包，第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。接下来我们主要从dp数组的定义方式、遍历顺序和几道经典的0-1背包问题来掌握解题的思路和方法。

2.1 dp数组的定义及其推导式

        对于0-1背包问题求解时的dp数组我们一般有两种定义方式：二维数组和滚动数组。在实际的刷题中我们习惯使用滚动数组的定义方式，因为写起来代码更为简便~~~下面我们接着上文中的标准0-1背包问题来写出对应的dp数组的定义及其推导式。

2.1.1 二维数组

dp[i][j]表示从下标为[0-i]的物品里任意取物品，放进容量为j的背包的最大价值总和。 

//相应的dp推导式如下：
dp[i][j] = max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j]);
//max中逗号左右两边分别代表取到i物品和不取i物品

得出相应的dp推导式后就需要将确定初始化条件了，当背包的容量为0时价值必然为0，因此dp[i][0]=0，但是dp[0][j]=value[0]，具体的初始化过程如下

vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
//之所以要初始化dp数组的大小为bagweight+1是因为我们需要遍历到j==bagweight的情况

确定完初始化条件我们需要确定遍历顺序了，在二维数组中，先遍历数组和先遍历物品都可以，都是正序遍历。

for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
 
    }
}

2.1.2 滚动数组

        滚动数组字面上有点抽象，其实滚动数组的方式是通过一个以为数组来实现上述二维数组的功能的，虽然不太好理解dp的含义但是却极大简洁了代码实现。简单来说其实滚动数组就是对每一维度的数组元素进行拷贝并将其数据进行覆盖，前面维度的数据都会加到当前维度上，以此来模拟二维数组的遍历过程。

dp[j]表示的含义是：装满容量为j的背包的最大价值总和。

//从二维数组转化到滚动数组其实很简单，只需要将i那个维度去掉就行
dp[j] = max(dp[j-weight[i]]+value[i],dp[j-1]);

那么滚动数组又应该如何来初始化呢？

首先我们确定了dp[i]的定义是容量为j的背包的最大价值总和，所以dp[0]自然就为0了。从递推公式中我们看出其余的dp数组元素都是由dp[0]推导出来的，所以索性都初始化为0。 

需要注意的是滚动数组的遍历顺序

在一维dp数组的遍历过程中，一定要先遍历物品再遍历背包，同时注意背包的遍历顺序是倒叙遍历的。倒叙遍历是为了每个物品只被添加过一次，这里之所以要先遍历物品再遍历背包是为了防止出现一个背包只放一个物品的情况。

 
vector<int> dp(bagWeight + 1, 0);
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]);
    }
}

为什么在二维数组中正序和倒序遍历均可？

这是因为在一维滚动数组中我们每一层的数据跟上一层是有关系的，而在二维数组中前后两层数据是隔离开来的，因此这时候需要倒序遍历。

为什么先遍历物品再遍历背包？

这是因为一维数组在dp前后两层之间有联系，如果将遍历背包放在外层循环的话，由于是倒序遍历我们背包中存放就只有一个物品的价值了。

2.2 0-1背包的经典例题

2.2.1 Leecode416.分割等和子集

题目描述：

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

提示：

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

输入样例：

        nums = [1,5,11,5]

输出样例：

        true

        这道题目其实比较容易想到转化成背包问题，题目要求划分成等和的两个子集，那么其实就是拿整个集合容量的一半容量大小的背包，看看物品是否能够装满它。荔枝在前面的介绍中提到了0-1背包问题中是会给出物品的weight数组和value数组，这道题目其实就是将整个集合中的元素按照大小关系划分为两个等和子集，这里我们将物品的values和weight等价于同一数值既可以将原问题转化成01背包问题。需要注意的是dp[i]的含义：它指的是容量为i的背包中可以放的数字总和的最大值，只有当容量为sum/2时候，dp[sum/2]=sum/2时可以将原来的数组分割成相同的两个子集。那么dp递推公式其实就呼之欲出了，就是最典型的0-1背包问题的dp公式。

代码示例：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int> weight = nums;
        int sum = 0;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        if(sum%2!=0) return false; //要想划分为等和子集就必须保证集合总和是一个偶数
        int bagweight = sum/2;
        vector<int> dp(10001,0);   //题目给出的数据范围来初始化，只用遍历到sum/2,而sum<20000
        for(int i=0;i<nums.size();i++){
            for(int j=bagweight;j>=nums[i];j--){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        } 
        if (dp[bagweight] == bagweight) return true;
        return false;
    }
};

来源：力扣（LeetCode）
链接： ​​​​​​​https://leetcode.cn/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 

2.2.2 Leecode494.目标和

题目描述：

        给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

输入样例：

        nums = [1,1,1,1,1], target = 3

输出样例：

        5

        对题目分析后我们发现其实这道题目跟前面的分割等和子集有点像，但是本题需要注意一下这几个关系：sum = left + right 、targer = left - right 。数学推导就可以得到left = (sum+target)/2，要满足这个关系，也就是要装满容量为left的背包一共有几种方法，这就转化成了一道0-1背包问题。接着确认dp[j]数组的含义：填满j（包括j）这么大容积的包，有dp[j]种方法。又因为要取到left这个值，所以初始化dp数组为vector<int> dp(left+1,0)。

代码示例：

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 left = (sum+target)/2;
        vector<int> dp(left+1,0);
        dp[0] = 1;
        for(int i=0;i<nums.size();i++){
            for(int j=left;j>=nums[i];j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[left];
    }
};

这道题目重点需要理解的就是dp递推式如何推导，这里我们需要想一下要填满一个容量为j的背包，如果我的手上有1，那么这一部分的数据就转换为填满容量为j-1的背包。题目要求的dp[j]其实就是将给出的元素数组中的元素被j减去所得到的容量的背包被装满总共有几种方法。因此dp递推式就是:

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

 要时刻谨记dp[j]的含义，要不然做题做着做着就混乱了~~~

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.2.3 Leecode474.一和零

题目描述：

        给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度，该子集中 最多有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集 。

输入样例：

        strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

输出样例：

        4

 这道题目有点意思它给出了两个维度要求m、n。因此滚动数组的形式也需要随之相应变化。我们首先确定dp数组的含义dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。这道题也是在求解最长子集的长度，只是在0和1的数量上有约束罢了，递推公式其实可以对比一个维度的0-1背包问题来设置即可。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // 两个维度的01背包问题
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(string str:strs){
            int numZero = 0;
            int numOne = 0;
            for(char c:str){
                if(c=='0') numZero++;
                else numOne++;
            }
            for(int i=m;i>=numZero;i--){
                for(int j=n;j>=numOne;j--){
                    dp[i][j] = max(dp[i][j],dp[i-numZero][j-numOne]+1);
                }
            }
        }
        return dp[m][n];
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ones-and-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

三、完全背包问题

        完全背包问题相比于0-1背包问题其实就是在遍历的顺序上做出了改变，这是由于背包问题的场景发生了改变而导致的。对于完全背包问题由于物品的数量是无限的，这时候就需要我们在背包的遍历顺序中修正一下，在前面讲滚动数组的时候我们为了保证背包中取得物品无重复而在遍历背包的时候采用逆序遍历，这时候就相应改成正序遍历即可。

由于遍历顺序的改变其实滚动数组的内外层for循环的先后遍历物品还是背包是有讲究的：对于排列问题就需要先遍历背包再遍历物品；对于组合问题就需要先遍历物品再遍历背包。

3.1 两种遍历顺序示例 

先遍历物品再遍历背包

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

先遍历背包再遍历物品

for(int j = 0; j <= bagWeight; j++) { // 遍历背包
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
    cout << endl;
}

3.2 完全背包问题典例

3.2.1 Leecode518.零钱兑换||

题目描述：

        给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个，题目数据保证结果符合 32 位带符号整数。

输入样例：

        amount = 5, coins = [1, 2, 5]

输出样例：

        4

根据题意我们首先设定dp数组的含义：凑成金额为i的组合数。体会一下这道题目其实就是再求装满背包的方法有几种，其实跟上面目标和的dp递推公式是一样的。

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

那么如何初始化呢？其实我们从常识来推论的话，amount=0时候的组合数应该为1，所以初始化dp[0] = 1;很明显这道题目是一道组合问题，那就确定下来是先遍历物品再遍历背包，至于为什么是这样子的遍历顺序其实荔枝感觉得自己假设一个用例下来手推一下dp过程就知道了。

代码示例：

//dp[i]：可以组成i的组合数。这里需要比较清晰地认知dp[i]的意义
//dp的递推公式：dp[j] += dp[j-coins[i]]
//初始化dp[0] = 1
class Solution {
public:
    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];
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/coin-change-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3.2.2 Leecode组合总和IV

题目描述：

        给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数，题目数据保证答案符合 32 位整数范围。

输入用例：    

        nums = [1,2,3], target = 4

输出用例：

        7

解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

        这道题目其实很简单，跟上述的零钱兑换||的思路是一样的，都是求装满背包有几种方法的类型，区别在于这道题目再输出样例中特别注明了顺序不同的序列视为不同组合，也就代表着这道题目是一个排列问题，这样子仅需要改变一下遍历的内外for循环的顺序即可。 

代码示例：

//这道题目跟前一道问题零钱兑换||的区别就在于这是一个排列问题，求的是将背包填满之后的一个排列数
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,0);
        dp[0] = 1;
        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.size();i++){
                if (j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3.2.3 Leecode70.爬楼梯 

        爬楼梯问题其实是刚开始学动态规划最经典的题目了，但一开始我们大多采用的是使用斐波那契数列的推导式子来推导dp递推式子，而在这里荔枝会给出如何用完全背包的思路来解决这道题目。

题目描述：

        假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入样例：

        n = 2
输出样例：

        2

爬楼梯如何转化成完全背包问题呢？其实我们可以将要爬的阶数v视作容量为v的背包，每一次爬其实就是在将一个价值和体积都为1或2的物品放入背包中，求的是装满背包的排列数。 

代码示例：

class Solution {
public:
    int climbStairs(int n) {
        // 使用完全背包问题的求解方法来求解
        vector<int> dp(n+1,0);
        dp[0] = 1;
        for(int j = 0;j<=n;j++){
            for(int i=1;i<=2;i++){
                if(j>=i){
                    dp[j]+=dp[j-i];
                }
            }
        }
        return dp[n];
    }
};
 
// 简单的斐波那契数列推导
// class Solution {
// public:
//     int climbStairs(int n) {
//         if(n<=1) return n;
//         vector<int> dp(n+1);
//         dp[1] = 1;
//         dp[2] = 2;
//         for(int i=3;i<=n;i++){
//             dp[i] = dp[i-1]+dp[i-2];
//         }
//         return dp[n];
//     }
// };

来源：力扣（LeetCode）
链接：​​​​​​​https://leetcode.cn/problems/climbing-stairs/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3.2.4 Leecode322.零钱兑换

题目描述：

        给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 ，你可以认为每种硬币的数量是无限的。

输入样例：

        coins = [1, 2, 5], amount = 11

输出样例：
        3

        首先我们需要弄清楚dp数组的含义dp[j]：凑足总额为j所需钱币的最少个数为dp[j]。由于题目要求的是求凑成目标金额的最少硬币数量，所以dp递推式需要修改成：dp[j] = min(dp[j - coins[i]] + 1, dp[j])，需要注意的是一个思维：这里通过转换我们已经将硬币面额作为了填满背包的weight，而其对于dp数组的value则是硬币数量，因此在递推公式中才是一个+1的操作。还有需要注意的是初始化的时候，由于我们求的是凑成目标面额的最少硬币数量，所以需要找一个最大值INT_MAX来初始化避免覆盖后面的dp递推值。

代码示例：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0] = 0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                if (dp[j - coins[i]] != INT_MAX) { //判断是能够凑出题目要求的数
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3.2.5 Leecode139.单词拆分

题目描述：

        给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入示例：

        s = "leetcode", wordDict = ["leet", "code"]

输出示例：

        true

        这道题目难点其实在于：对于STL库不太熟悉或者对于字符处理的题目不太熟悉的同学会不清楚使用unordered_set来处理字符。首先确定dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

代码示例：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1,false);
        dp[0] = true;
        for(int i=1;i<=s.size();i++){  //遍历背包
            for(int j=0;j<i;j++){      //遍历物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

四、多重背包问题

        荔枝在前面有提及多重背包问题最主要的特征就是有多个种类的物品且数量不同，有一种常见的处理思路就是将多重背包问题中的所有物品不按类分而是一一摊开，这样就把一个多重背包问题转化成一个0-1背包问题。Carl哥给出了具体的模拟过程：

void test_multi_pack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }
 
    vector<int> dp(bagWeight + 1, 0);
    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]);
        }
        for (int j = 0; j <= bagWeight; j++) {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;
 
}
int main() {
    test_multi_pack();
}

---

总结

        在这篇文章中，荔枝主要侧重讲了0-1背包问题和完全背包问题以及相应的变式和应用。其实一整个流程刷下来发现其实这些题目都是遵循着某个规律。其中最主要的就是要谨记dp数组的含义以及如何取递推，同样的遍历顺序和初始化有时候也很难抉择。这其实就是动态规划的难点。写了三个钟总算整理好了背包系列，荔枝整理完了感觉确实对于背包问题的思路更加清晰了，荔枝也希望在上面的题目中的解析能够帮助到正在学习的小伙伴~~~

今朝已然成为过去，明日依然向往未来！我是小荔枝，在技术成长的路上与你相伴，码文不易，麻烦举起小爪爪点个赞吧哈哈哈~~~ 比心心♥~~~