文章目录【1049.最后一块石头的重量II】【494.目标和】二维dp数组一维dp数组【474.一和零】【1049.最后一块石头的重量II】思路本题其实是尽量让石头分成重量相同的两堆尽可能相同相撞之后剩下的石头就是最小的。一堆的石头重量是sum那么我们就尽可能拼成重量为 sum / 2 的石头堆。 这样剩下的石头堆也是尽可能接近 sum/2 的重量。 那么此时问题就是有一堆石头每个石头都有自己的重量是否可以装满最大重量为 sum / 2的背包。classSolution{public:intlastStoneWeightII(vectorintstones){intsum0;for(inti0;istones.size();i){sumstones[i];}if(sum1)return1;inttargetsum/2;// dp[target]表示容量为target的背包最多可以装多少重量石头vectorintdp(15001,0);for(inti0;istones.size();i){for(intjtarget;jstones[i];j--){dp[j]max(dp[j],dp[j-stones[i]]stones[i]);// 在计算target的时候target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]的。}}returnsum-dp[target]-dp[target];}};【494.目标和】思路二维dp数组假设加法的总和为x那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) targetx (target sum) / 2此时问题就转化为用nums装满容量为x的背包有几种方法。这里的x就是bagSize也就是我们后面要求的背包容量。看到(target sum) / 2应该担心计算的过程中向下取整有没有影响。且这么担心是有道理的例如sum是5target是2 的话其实就是无解的所以C代码中输入的S 就是题目描述的 targetif((targetsum)%21)return0;// 此时没有方案同时如果target 的绝对值已经大于sum那么也是没有方案的。if(abs(target)sum)return0;// 此时没有方案因为每个物品题目中的1只用一次这次和之前遇到的背包问题不一样了之前都是求容量为j的背包最多能装多少。本题则是装满有几种方法。其实这就是一个组合问题了。确定dp数组及下标的含义dp[i] [j]使用下标为[0,i]的nums[i]能够凑满j包括j这么大容量的包有dp[i] [j]这么多种方法。确定递推公式抽象化如下不放物品i即背包容量为j里面不放物品i装满有dp[i - 1] [j]中方法。放物品i 即先空出物品i的容量背包容量为j - 物品i容量放满背包有 dp[i - 1] [j - 物品i容量] 种方法。本题中物品i的容量是nums[i]价值也是nums[i]。递推公式dp[i] [j] dp[i - 1] [j] dp[i - 1] [j - nums[i]];看到这个递推公式我们应该注意到j - nums[i]作为数组下标如果j - nums[i]小于零呢说明背包容量装不下 物品i所以此时装满背包的方法值 等于 不放物品i的装满背包的方法即dp[i] [j] dp[i - 1] [j];所以递推公式if(nums[i]j)dp[i][j]dp[i-1][j];elsedp[i][j]dp[i-1][j]dp[i-1][j-nums[i]];dp数组如何初始化求解dp[i] [j]是有其左上方和上方推出因此二维数组的最上行和最左列必须初始化。关于dp[0] [0]的值在上面的递推公式讲解中已经讲过装满背包容量为0 的方法数量是1即 放0件物品。那么最上行dp[0] [j] 如何初始化呢dp[0] [j]只放物品0 把容量为j的背包填满有几种方法。只有背包容量为 物品0 的容量的时候方法为1正好装满。其他情况下要不是装不满要不是装不下。所以初始化dp[0] [nums[0]] 1 其他均为0 。表格最左列也要初始化dp[i] [0] : 背包容量为0 放物品0 到 物品i装满有几种方法。都是有一种方法就是放0件物品。即 dp[i] [0] 1但这里有例外就是如果物品数值就是0呢如果有两个物品物品0为0 物品1为0装满背包容量为0的方法有几种。放0件物品放物品0放物品1放物品0 和 物品1此时是有4种方法。其实就是算数组里有t个0然后按照组合数量求即 2^t 。初始化如下intnumZero0;for(inti0;inums.size();i){if(nums[i]0)numZero;dp[i][0](int)pow(2.0,numZero);}确定遍历顺序明确递推方向时我们知道当前值是由上方和左上方推出。那么我们的遍历顺序一定是从上到下从左到右。因为只有这样我们才能基于之前的数值做推导。先从上到下 再从左到右遍历例如这样for(inti1;inums.size();i){// 行遍历物品for(intj0;jbagSize;j){// 列遍历背包}}先从左到右再从上到下例如这样for(intj0;jbagSize;j){// 列遍历背包for(inti1;inums.size();i){// 行遍历物品}}以上两种遍历都可以 但仅针对二维DP数组是这样的举例推导dp数组代码解答// 二维dp解法classSolution{public:intfindTargetSumWays(vectorintnums,inttarget){intsum0;for(inti0;inums.size();i)sumnums[i];if(abs(target)sum)return0;// 此时没有方案if((targetsum)%21)return0;// 此时没有方案intbagSize(targetsum)/2;/* 假设加法的总和为x那么减法对应的总和就是sum - x。 所以我们要求的是 x - (sum - x) target x (target sum) / 2 此时问题就转化为用nums装满容量为x的背包有几种方法。 */vectorvectorintdp(nums.size(),vectorint(bagSize1,0));// 初始化最上行if(nums[0]bagSize)dp[0][nums[0]]1;//初始化最左列dp[0][0]1;intnumZero0;for(inti0;inums.size();i){if(nums[i]0)numZero;dp[i][0](int)pow(2.0,numZero);}// 以下遍历顺序可以颠倒for(inti1;inums.size();i){// 行遍历物品for(intj0;jbagSize;j){// 列 遍历背包容量if(nums[i]j)dp[i][j]dp[i-1][j];elsedp[i][j]dp[i-1][j]dp[i-1][j-nums[i]];}}returndp[nums.size()-1][bagSize];}};一维dp数组确定dp数组及下标含义将二维dp数组压缩成一维dp数组即滚动数组原理是一样的即重复利用每一行的数值。既然是重复利用每一行就是将二维数组压缩成一行。dp[i] [j] 去掉行的维度即 dp[j]表示填满j包括j这么大容积的包有dp[j]种方法。确定递推公式二维DP数组递推公式dp[i][j] dp[i - 1][j] dp[i - 1][j - nums[i]];去掉维度i 之后递推公式dp[j] dp[j] dp[j - nums[i]]即dp[j] dp[j - nums[i]]这个公式在后面在背包解决排列组合问题的时候还会用到dp数组如何初始化在上面二维dp数组中我们讲解过 dp[0] [0] 初始为1这里dp[0] 同样初始为1 ,即装满背包为0的方法有一种放0件物品。确定递推顺序和前面的一维dp数组方法一样遍历物品放在外循环遍历背包在内循环且内循环倒序为了保证物品只使用一次。举例推导dp数组代码解答// 一维dp解法classSolution{public:intfindTargetSumWays(vectorintnums,inttarget){intsum0;for(inti0;inums.size();i)sumnums[i];if(abs(target)sum)return0;if((targetsum)%21)return0;intbagSize(targetsum)/2;vectorintdp(bagSize1,0);// dp[j]表示填满j包括j这么大容积的包有dp[j]种方法。dp[0]1;for(inti0;inums.size();i){for(intjbagSize;jnums[i];j--){dp[j]dp[j-nums[i]];}}returndp[bagSize];}};【474.一和零】思路多重背包是每个物品数量不同的情况。本题中strs 数组里的元素就是物品每个物品都是一个而m 和 n相当于是一个背包两个维度的背包。切勿把m和n混淆为物品了感觉这是不同数量的物品那就理解错成是多重背包了。但本题其实是01背包问题只不过这个背包有两个维度一个是m一个是n而不同长度的字符串就是不同大小的待装物品。确定dp数组及其下标含义dp[i] [j]最多有i个0和j个1的strs的最大子集的大小为dp[i] [j]。确定递推公式dp[i] [j] 可以由前一个strs里的字符串推导出来strs里的字符串有zeroNum个0oneNum个1。dp[i] [j] 就可以是 dp[i - zeroNum] [j - oneNum] 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背包只不过物品的重量有了两个维度而已。dp数组如何初始化01背包的dp数组初始化为0就可以。因为物品价值不会是负数初始为0保证递推的时候dp[i] [j]不会被初始值覆盖。确定遍历顺序01背包为什么一定是外层for循环遍历物品内层for循环遍历背包容量且从后向前遍历for(string str:strs){// 遍历物品intoneNum0,zeroNum0;for(charc:str){if(c0)zeroNum;elseoneNum;}for(intim;izeroNum;i--){// 遍历背包容量且从后向前遍历for(intjn;joneNum;j--){dp[i][j]max(dp[i][j],dp[i-zeroNum][j-oneNum]1);}}}举例推导dp数组代码classSolution{public:intfindMaxForm(vectorstringstrs,intm,intn){vectorvectorintdp(m1,vectorint(n1,0));// 默认初始化0// dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。for(string str:strs){// 外层遍历物品intoneNum0,zeroNum0;for(charc:str){if(c0)zeroNum;elseoneNum;}for(intim;izeroNum;i--){// 内层两个维度都要倒序遍历for(intjn;joneNum;j--){dp[i][j]max(dp[i][j],dp[i-zeroNum][j-oneNum]1);}}}returndp[m][n];}};