文章目录
- 【1049.最后一块石头的重量II】
- 【494.目标和】
- 二维dp数组：
- 一维dp数组：
- 【474.一和零】
【1049.最后一块石头的重量II】
思路：
本题其实是尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的。
一堆的石头重量是sum，那么我们就尽可能拼成重量为 sum / 2 的石头堆。 这样剩下的石头堆也是尽可能接近 sum/2 的重量。 那么此时问题就是有一堆石头，每个石头都有自己的重量，是否可以装满最大重量为 sum / 2的背包。
classSolution{public:intlastStoneWeightII(vector<int>&stones){intsum=0;for(inti=0;i<stones.size();i++){sum+=stones[i];}if(sum==1)return1;inttarget=sum/2;// dp[target]表示容量为target的背包最多可以装多少重量石头vector<int>dp(15001,0);for(inti=0;i<stones.size();i++){for(intj=target;j>=stones[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) = target
x = (target + sum) / 2
此时问题就转化为，用nums装满容量为x的背包，有几种方法。
这里的x，就是bagSize，也就是我们后面要求的背包容量。
看到(target + sum) / 2应该担心计算的过程中向下取整有没有影响。
且这么担心是有道理的，例如sum是5，target是2 的话其实就是无解的，所以：
（C++代码中，输入的S 就是题目描述的 target）if((target+sum)%2==1)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 。
初始化如下：
intnumZero=0;for(inti=0;i<nums.size();i++){if(nums[i]==0)numZero++;dp[i][0]=(int)pow(2.0,numZero);}- 确定遍历顺序
明确递推方向时，我们知道当前值是由上方和左上方推出。
那么我们的遍历顺序一定是从上到下，从左到右。
因为只有这样，我们才能基于之前的数值做推导。
先从上到下 ，再从左到右遍历，例如这样：
for(inti=1;i<nums.size();i++){// 行，遍历物品for(intj=0;j<=bagSize;j++){// 列，遍历背包}}先从左到右，再从上到下，例如这样：
for(intj=0;j<=bagSize;j++){// 列，遍历背包for(inti=1;i<nums.size();i++){// 行，遍历物品}}以上两种遍历都可以！ （但仅针对二维DP数组是这样的）
- 举例推导dp数组
代码解答：
// 二维dp解法classSolution{public:intfindTargetSumWays(vector<int>&nums,inttarget){intsum=0;for(inti=0;i<nums.size();i++)sum+=nums[i];if(abs(target)>sum)return0;// 此时没有方案if((target+sum)%2==1)return0;// 此时没有方案intbagSize=(target+sum)/2;/* 假设加法的总和为x，那么减法对应的总和就是sum - x。 所以我们要求的是 x - (sum - x) = target x = (target + sum) / 2 此时问题就转化为，用nums装满容量为x的背包，有几种方法。 */vector<vector<int>>dp(nums.size(),vector<int>(bagSize+1,0));// 初始化最上行if(nums[0]<=bagSize)dp[0][nums[0]]=1;//初始化最左列dp[0][0]=1;intnumZero=0;for(inti=0;i<nums.size();i++){if(nums[i]==0)numZero++;dp[i][0]=(int)pow(2.0,numZero);}// 以下遍历顺序可以颠倒for(inti=1;i<nums.size();i++){// 行，遍历物品for(intj=0;j<=bagSize;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(vector<int>&nums,inttarget){intsum=0;for(inti=0;i<nums.size();i++)sum+=nums[i];if(abs(target)>sum)return0;if((target+sum)%2==1)return0;intbagSize=(target+sum)/2;vector<int>dp(bagSize+1,0);// dp[j]，表示：填满j（包括j）这么大容积的包，有dp[j]种方法。dp[0]=1;for(inti=0;i<nums.size();i++){for(intj=bagSize;j>=nums[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个0，oneNum个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){// 遍历物品intoneNum=0,zeroNum=0;for(charc:str){if(c=='0')zeroNum++;elseoneNum++;}for(inti=m;i>=zeroNum;i--){// 遍历背包容量且从后向前遍历！for(intj=n;j>=oneNum;j--){dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}- 举例推导dp数组
代码：
classSolution{public:intfindMaxForm(vector<string>&strs,intm,intn){vector<vector<int>>dp(m+1,vector<int>(n+1,0));// 默认初始化0// dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。for(string str:strs){// 外层遍历物品intoneNum=0,zeroNum=0;for(charc:str){if(c=='0')zeroNum++;elseoneNum++;}for(inti=m;i>=zeroNum;i--){// 内层两个维度都要倒序遍历for(intj=n;j>=oneNum;j--){dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}returndp[m][n];}};
