文章目录完全背包二维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(inti1;iweight.size();i){// 当然这一步如果把dp数组预先初始化为0了这一步就可以省略dp[i][0]0;}// 正序遍历如果能放下就一直装物品0for(intjweight[0];jbagWeight;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更方便一些。最后初始化代码如下// 初始化 dpvectorvectorintdp(weight.size(),vectorint(bagweight1,0));for(intjweight[0];jbagWeight;j){dp[0][j]dp[0][j-weight[0]]value[0];}确定遍历顺序01背包二维DP数组先遍历物品还是先遍历背包都是可以的。因为两种遍历顺序对于二维dp数组来说递推公式所需要的值二维dp数组里对应的位置都有。既可以先遍历物品再遍历背包for(inti1;in;i){// 遍历物品for(intj0;jbagWeight;j){// 遍历背包容量if(jweight[i])dp[i][j]dp[i-1][j];elsedp[i][j]max(dp[i-1][j],dp[i][j-weight[i]]value[i]);}}也可以先遍历背包再遍历物品for(intj0;jbagWeight;j){// 遍历背包容量for(inti1;in;i){// 遍历物品if(jweight[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数组解法#includeiostream#includevectorusingnamespacestd;intmain(){intn,v;// nv分别表示研究材料的种类和行李所能承担的总重量cinnv;vectorintweight(n,0);vectorintvalues(n,0);for(inti0;in;i){cinweight[i]values[i];}vectorvectorintdp(n,vectorint(v1,0));// dp[i][j]表示从行李0i中在背包容量为j的时候可携带的最大价值// 初始化for(intjweight[0];jv;j){dp[0][j]dp[0][j-weight[0]]values[0];}// 遍历for(inti1;in;i){for(intj0;jv;j){if(jweight[i])dp[i][j]dp[i-1][j];elsedp[i][j]max(dp[i-1][j],dp[i][j-weight[i]]values[i]);}}coutdp[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(intj0;jbagWeight;j){// 遍历背包容量for(inti0;iweight.size();i){// 遍历物品if(j-weight[i]0)dp[j]max(dp[j],dp[j-weight[i]]value[i]);}coutendl;}先遍历物品再遍历背包for(inti0;iweight.size();i){// 遍历物品for(intj0;jbagWeight;j){// 遍历背包容量if(j-weight[i]0)dp[j]max(dp[j],dp[j-weight[i]]value[i]);}}// 一维dp数组解法#includeiostream#includevectorusingnamespacestd;intmain(){intn,v;// nv分别表示研究材料的种类和行李所能承担的总重量cinnv;vectorintweight(n,0);vectorintvalues(n,0);for(inti0;in;i){cinweight[i]values[i];}vectorintdp(v1,0);// dp[i]表示背包重量为i的时候可以携带的最大价值for(inti0;in;i){// 遍历物品for(intj1;jv;j){// 遍历背包重量if(jweight[i])dp[j]max(dp[j],dp[j-weight[i]]values[i]);}}coutdp[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(intj0;jbagSize;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,vectorintcoins){intbagSizeamount;vectorvectoruint64_tdp(coins.size(),vectoruint64_t(bagSize1,0));// dp[i][j]表示从0i中选有多少种方法凑到amountjfor(inti0;ibagSize;i){if(i%coins[0]0)dp[0][i]1;}for(intj0;jcoins.size();j){dp[j][0]1;}for(inti1;icoins.size();i){for(intj0;jbagSize;j){if(jcoins[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(inti0;icoins.size();i){// 遍历物品for(intjcoins[i];jamount;j){// 遍历背包容量dp[j]dp[j-coins[i]];}}假设coins[0] 1coins[1] 5。那么就是先把1加入计算然后再把5加入计算得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。所以这种遍历顺序中dp[j]里计算的是组合数如果把两个for交换顺序代码如下for(intj0;jamount;j){// 遍历背包容量for(inti0;icoins.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,vectorintcoins){intbagSizeamount;vectoruint64_tdp(bagSize1,0);// dp[i]表示总数容量为i能凑出的方法数dp[0]1;for(inti0;icoins.size();i){for(intjcoins[i];jbagSize;j){dp[j]dp[j-coins[i]];}}returndp[bagSize];}};【377.组合总和Ⅳ】思路和上一题一样重点在遍历顺序如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。// 一维dp数组classSolution{public:intcombinationSum4(vectorintnums,inttarget){vectoruint32_tdp(target1,0);//dp[i]表示target为i时能凑出的方法数dp[0]1;for(inti0;itarget;i){for(intj0;jnums.size();j){if(i-nums[j]0dp[i]INT_MAX-dp[i-nums[j]]){dp[i]dp[i-nums[j]];}}}returndp[target];}};【70.爬楼梯进阶版】思路看出来是求排列数的完全背包即可。#includeiostream#includevectorusingnamespacestd;intmain(){intn,m;cinnm;// n就是target0m就是每次完全背包可选择的数vectorintdp(n1,0);dp[0]1;for(inti1;in;i){// 遍历背包容量for(intj1;jm;j){// 遍历物品容量if(ij)dp[i]dp[i-j];}}coutdp[n]endl;return0;}