文章目录
- 完全背包：
- 二维dp数组
- 【52.携带研究材料】
- 一维dp数组
- 【518.零钱兑换II】
- 二维dp数组解法：
- 一维dp数组解法：
- 【377.组合总和Ⅳ】
- 【70.爬楼梯（进阶版）】
完全背包：
二维dp数组
定义：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
- 确定dp数组及其下标的含义：
dp[i] [j] 表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。
- 确定递推公式：
在01背包中，背包先空留出物品1的容量，此时容量为1，只考虑放物品0的最大价值是 dp[0] [1]，因为01背包每个物品只有一个，既然空出物品1，那背包中也不会再有物品1！
而在完全背包中，物品是可以放无限个，所以 即使空出物品1空间重量，那背包中也可能还有物品1，所以此时我们依然考虑放 物品0 和 物品1 的最大价值即：dp[1] [1]， 而不是 dp[0] [1]
所以放物品1的情况 = dp[1] [1] + 物品1的价值
以上过程，抽象化如下：
- 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1] [j]。
- 放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i] [j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i] [j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
递推公式：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
（注意，完全背包二维dp数组 和 01背包二维dp数组 递推公式的区别，01背包中是max(dp[i - 1] [j] , dp[i - 1] [j - weight[i]] + value[i])）
- dp数组如何初始化：
首先从dp[i] [j]的定义出发，如果背包容量j为0的话，即dp[i] [0]，无论是选取哪些物品，背包价值总和一定为0。
再看其他情况。
状态转移方程dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);可以看出有一个方向 i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
dp[0] [j]，即：存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当j < weight[0]的时候，dp[0] [j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0] [j] 如果能放下weight[0]的话，就一直装，每一种物品有无限个。
代码初始化如下：
for(inti=1;i<weight.size();i++){// 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略dp[i][0]=0;}// 正序遍历，如果能放下就一直装物品0for(intj=weight[0];j<=bagWeight;j++)dp[0][j]=dp[0][j-weight[0]]+value[0];从递归公式： dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - weight[i]] + value[i]); 可以看出dp[i] [j] 是由上方和左方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。
但只不过一开始就统一把dp数组统一初始为0，更方便一些。
最后初始化代码如下：
// 初始化 dpvector<vector<int>>dp(weight.size(),vector<int>(bagweight+1,0));for(intj=weight[0];j<=bagWeight;j++){dp[0][j]=dp[0][j-weight[0]]+value[0];}- 确定遍历顺序
01背包二维DP数组，先遍历物品还是先遍历背包都是可以的。
因为两种遍历顺序，对于二维dp数组来说，递推公式所需要的值，二维dp数组里对应的位置都有。
既可以先遍历物品再遍历背包：
for(inti=1;i<n;i++){// 遍历物品for(intj=0;j<=bagWeight;j++){// 遍历背包容量if(j<weight[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);}}也可以先遍历背包再遍历物品：
for(intj=0;j<=bagWeight;j++){// 遍历背包容量for(inti=1;i<n;i++){// 遍历物品if(j<weight[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);}}- 举例推导dp数组
【52.携带研究材料】
// 二维dp数组解法#include<iostream>#include<vector>usingnamespacestd;intmain(){intn,v;// n，v，分别表示研究材料的种类和行李所能承担的总重量cin>>n>>v;vector<int>weight(n,0);vector<int>values(n,0);for(inti=0;i<n;i++){cin>>weight[i]>>values[i];}vector<vector<int>>dp(n,vector<int>(v+1,0));// dp[i][j]表示从行李0～i中在背包容量为j的时候可携带的最大价值// 初始化for(intj=weight[0];j<=v;j++){dp[0][j]=dp[0][j-weight[0]]+values[0];}// 遍历for(inti=1;i<n;i++){for(intj=0;j<=v;j++){if(j<weight[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+values[i]);}}cout<<dp[n-1][v]<<endl;return0;}一维dp数组
压缩成一维DP数组，也就是将上一层拷贝到当前层。
将上一层dp[i-1] 的那一层拷贝到 当前层 dp[i] ，那么 递推公式由：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])变成：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
这里有录友想，这样拷贝的话， dp[i - 1][j] 的数值会不会 覆盖了 dp[i][j] 的数值呢？
并不会，因为 当前层 dp[i][j] 是空的，是没有计算过的。
变成dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])我们压缩成一维dp数组，去掉 i 层数维度。
即：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
遍历顺序是重点：
01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！
因为dp[j]是根据下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）。
先遍历背包再遍历物品，代码如下：
for(intj=0;j<=bagWeight;j++){// 遍历背包容量for(inti=0;i<weight.size();i++){// 遍历物品if(j-weight[i]>=0)dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}cout<<endl;}先遍历物品再遍历背包：
for(inti=0;i<weight.size();i++){// 遍历物品for(intj=0;j<=bagWeight;j++){// 遍历背包容量if(j-weight[i]>=0)dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}// 一维dp数组解法#include<iostream>#include<vector>usingnamespacestd;intmain(){intn,v;// n，v，分别表示研究材料的种类和行李所能承担的总重量cin>>n>>v;vector<int>weight(n,0);vector<int>values(n,0);for(inti=0;i<n;i++){cin>>weight[i]>>values[i];}vector<int>dp(v+1,0);// dp[i]表示背包重量为i的时候可以携带的最大价值for(inti=0;i<n;i++){// 遍历物品for(intj=1;j<=v;j++){// 遍历背包重量if(j>=weight[i])dp[j]=max(dp[j],dp[j-weight[i]]+values[i]);}}cout<<dp[v]<<endl;return0;}注意：对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
但如果题目稍稍有点变化，就会体现在遍历顺序上。
如果问装满背包有几种方式的话？ 那么两个for循环的先后顺序就有很大区别了。
【518.零钱兑换II】
思路：
二维dp数组解法：
- 确定dp数组以及下标的含义：
定义二维dp数值 dp[i[j]：使用 下标为[0, i]的coins[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种组合方法。
- 确定递推公式：
本题和 494. 目标和 是一样的，唯一区别就是 494. 目标和 是 01背包，本题是完全背包。
在494. 目标和中详解讲解了装满背包有几种方法，二维DP数组的递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
所以本题递推公式：**dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]]**，区别依然是dp[i - 1][j - nums[i]]和dp[i][j - nums[i]]
这个 ‘所以’ 省略了很多推导的内容，具体内容可在 494. 目标和 和 完全背包理论基础 中找寻。
- dp数组如何初始化：
最上行dp[0] [j] 如何初始化：
dp[0] [j]的含义：用物品0（即coins[0]）装满背包容量为j的背包，有几种组合方法。
如果 j 可以整除 物品0，那么装满背包就有1种组合方法。
初始化代码：
for(intj=0;j<=bagSize;j++){if(j%coins[0]==0)dp[0][j]=1;}最左列如何初始化：
dp[i] [0] 的含义：用物品i（即coins[i]）装满容量为0的背包有几种组合方法。
都有一种方法，即不装。
所以 dp[i] [0] 都初始化为1。
- 确定遍历顺序
二维DP数组的完全背包的两个for循环先后顺序是无所谓的。
先遍历背包，还是先遍历物品都是可以的i
- 打印dp数组
// 二维dp数组classSolution{public:intchange(intamount,vector<int>&coins){intbagSize=amount;vector<vector<uint64_t>>dp(coins.size(),vector<uint64_t>(bagSize+1,0));// dp[i][j]表示从0～i中选有多少种方法凑到amount=jfor(inti=0;i<=bagSize;i++){if(i%coins[0]==0)dp[0][i]=1;}for(intj=0;j<coins.size();j++){dp[j][0]=1;}for(inti=1;i<coins.size();i++){for(intj=0;j<=bagSize;j++){if(j<coins[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];}}returndp[coins.size()-1][bagSize];}};一维dp数组解法：
- 确定dp数组以及下标的含义
dp[j]：凑成总金额j的货币组合数为dp[j]
- 确定递推公式
本题二维dp 递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]
压缩成一维：dp[j] += dp[j - coins[i]]
- dp数组如何初始化
装满背包容量为0 的方法是1，即不放任何物品，dp[0] = 1
- 确定遍历顺序
在完全背包（一维DP）中讲解了完全背包的两个for循环的先后顺序都是可以的。
但本题就不行了！
因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！
而本题要求凑成总和的组合数，元素之间明确要求没有顺序。
所以纯完全背包是能凑成总和就行，不用管怎么凑的。
本题是求凑出来的方案个数，且每个方案个数是组合数。
那么本题，两个for循环的先后顺序可就有说法了。
我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。
代码如下：
for(inti=0;i<coins.size();i++){// 遍历物品for(intj=coins[i];j<=amount;j++){// 遍历背包容量dp[j]+=dp[j-coins[i]];}}假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：
for(intj=0;j<=amount;j++){// 遍历背包容量for(inti=0;i<coins.size();i++){// 遍历物品if(j-coins[i]>=0)dp[j]+=dp[j-coins[i]];}}背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
- 举例推导dp数组
classSolution{public:intchange(intamount,vector<int>&coins){intbagSize=amount;vector<uint64_t>dp(bagSize+1,0);// dp[i]表示总数容量为i能凑出的方法数dp[0]=1;for(inti=0;i<coins.size();i++){for(intj=coins[i];j<=bagSize;j++){dp[j]+=dp[j-coins[i]];}}returndp[bagSize];}};【377.组合总和Ⅳ】
思路：
和上一题一样，重点在遍历顺序：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
// 一维dp数组classSolution{public:intcombinationSum4(vector<int>&nums,inttarget){vector<uint32_t>dp(target+1,0);//dp[i]表示target为i时能凑出的方法数dp[0]=1;for(inti=0;i<=target;i++){for(intj=0;j<nums.size();j++){if(i-nums[j]>=0&&dp[i]<=INT_MAX-dp[i-nums[j]]){dp[i]+=dp[i-nums[j]];}}}returndp[target];}};【70.爬楼梯（进阶版）】
思路：
看出来是求排列数的完全背包即可。
#include<iostream>#include<vector>usingnamespacestd;intmain(){intn,m;cin>>n>>m;// n就是target，0～m就是每次完全背包可选择的数vector<int>dp(n+1,0);dp[0]=1;for(inti=1;i<=n;i++){// 遍历背包容量for(intj=1;j<=m;j++){// 遍历物品容量if(i>=j)dp[i]+=dp[i-j];}}cout<<dp[n]<<endl;return0;}
