- 1JUC相关问题（1）_concurrent集合类
- 2什么是块级元素和内联级元素
- 3ThinkPHP5 集成使用 GatewayWorker 进行即时通信的配置操作_gatewayworker未读消息
- 4上传本地项目到Gitee_使用黑窗口上传文件夹到gitte
- 5安卓手机/pad用Charles抓包https（mac版超详细教程)_charles 安卓抓包
- 6微信查看对方撤回的消息，只需打开这个功能，一眼便知_微信撤回消息怎么看csdn
- 7Python调用文心千帆的API_python 调用千帆api
- 8深度学习500问——Chapter07：生成对抗网络（GAN）（2）
- 9基于kintex UltraScale XCKU060的双路QSFP+光纤PCIe 卡
- 102024最新AI系统【SparkAI】，ChatGPT商业运营版系统源码/ai问答/ai绘画/GPTs，SunoAI音乐生成大模型/带分销AIGC搭建部署教程
动态规划——01背包，完全背包，力扣题型讲解
赞
踩
目录
背包问题
本文带你解决力扣上所有典型的背包问题，通俗易懂的讲解。
对于大厂面试题，只需要掌握01背包和完全背包问题即可。
（本文是跟随代码随想录所学而记的笔记）
01背包及基础
怎么取能使价值更大？
暴⼒的解法应该是怎么样的呢？ 每⼀件物品其实只有两个状态，取或者不取，所以可以使⽤回溯法搜索出所有的情况，那么时间复杂度 就是O(2^n)，这⾥的n表示物品数量。 所以暴⼒的解法是指数级别的时间复杂度。进⽽才需要动态规划的解法来进⾏优化！
依然动规五部曲分析⼀波。
1. 确定dp数组以及下标的含义
对于背包问题，有⼀种写法， 是使⽤⼆维数组，即dp[i][j] 表示从下标为[0-i]的物品⾥任意取，放进容量 为j的背包，价值总和最⼤是多少。
所以我们需要初始化第一行第一列。
完整代码：
压缩空间（一维dp滚动数组）
在使⽤⼆维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那⼀层拷⻉到dp[i]上，表达式完全可以是：
dp[i][j] = max(dp[i][j], dp[i][ j - weight[i]] + value[i]);
于其把dp[i - 1]这⼀层拷⻉到dp[i]上，不如只⽤⼀个⼀维数组了，只⽤dp[j]（⼀维数组，也可以理解是 ⼀个滚动数组）
这就是滚动数组的由来，需要满⾜的条件是上⼀层可以重复利⽤，直接拷⻉到当前层。
动规五步曲：
1. 确定dp数组的定义
回顾一下二维dp数组中i和j的含义：
dp[i][j] 表示从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少。
那我们进行压缩后，核心思想是把第i行的数据拷贝到第i+1行上，那此时变成一维后，dp[j]代表的就是循环第i轮时，容量为j的背包最大价值为dp[j]。
2. ⼀维dp数组的递推公式
dp[j]可以通过dp[j - weight[j]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最⼤价 值。
dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背 包，放⼊物品i了之后的价值即：dp[j]）
此时dp[j]有两个选择，⼀个是取⾃⼰dp[j]，⼀个是取dp[j - weight[i]] + value[i]，指定是取最⼤的，毕竟是求最⼤价值， 所以递归公式为
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3. ⼀维dp数组如何初始化
此处的初始化，dp[j]代表容量为j的物品的最大价值。
初始化时，我们可以放入第一个物品，然后循环的时候i从第二个物品开始循环，不过也可以不考虑第一个物品，都可以，这种情况全部初始化为0即可。（因为此时没有物品，价值自然为0）
因为如果是二维的话，代码是写的第i-1行，所以i的第0行需要初始化才能方便后面的填表。
不过如果是一维的情况，就没有第i-1行了，所以初始化考不考虑第一个物品都可以。
但是有一点需要注意！如果价值里面有负数！！那么⾮0下标就要初始化为负⽆穷。
这样才能让dp数组在递归公式的过程中取的最⼤的价值，⽽不是被初始值覆盖了。
4. ⼀维dp数组遍历顺序
先给出结论
我们可以发现，我们对于j，是从末尾往前循环，而不是正序，这是为什么呢？
如果是二维数组，第i行的值是由第i-1行决定的，也就是说第i行的第j列的dp值如何改变，都不会影响第i行后续其他的dp值。
但是如果是一维数组，此时我们是用当前行的值代替上一行来计算，如果我们在前面改变了第j列的值，那很可能会影响第j列后面的dp值，因为此时该dp值不再是由所谓的“上一行”来决定的了，而是会受到当前行的影响！
那为什么要从后往前遍历呢？因为第j列的值只会受到第j列和其前面的列数影响，不会受到后面的列数影响。换言之即使后面改变了也不会影响前面的！
5. 举例推导dp数组
代码如下：
- void test_1_wei_bag_problem() {
- vector<int> weight = {1, 3, 4};
- vector<int> value = {15, 20, 30};
- int bagWeight = 4;
- // 初始化
- 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]);
- }
- }
- cout << dp[bagWeight] << endl;
- }
- int main() {
- test_1_wei_bag_problem();
- }
416.分割等和子集
本题和下面这两题也很类似：
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
先回到本题看看，本题可以直接用递归法解决，但是会超时。
解法如下：
- class Solution {
- public:
- vector<int> num;
- double allSum=0;
- bool findFlag=false;
- bool canPartition(vector<int>& nums) {
- for(auto val:nums)allSum+=val;
- num=nums;
- dfs(0,0);
- return findFlag;
- }
- void dfs(double nowSum,int index){
- if(index>=num.size())return;
- if(nowSum==allSum/2){
- findFlag=true;
- return;
- }
- else{
- dfs(nowSum+num[index],index+1);
- dfs(nowSum,index+1);
- }
- }
- };
或者将bool变量作为返回值也是可以的，两种代码仅仅改了判断true和false的方式。
动规五部曲分析如下：
1. 确定dp数组以及下标的含义
01背包中，dp[i] 表示： 容量为j的背包，所背的物品价值可以最⼤为dp[j]。
套到本题，dp[i]表示 背包总容量是i，最⼤可以凑成i的⼦集总和为dp[i]。
（使用压缩后的一维数组）
2. 确定递推公式
01背包的递推公式为：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题，相当于背包⾥放⼊数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
3. dp数组如何初始化
首先dp[0]一定是0，如果题目价值给的都是正整数，那么初始化全为0即可。如果价值中出现负数，非0下标就要全部初始化为负无穷。
此处有一点初始化，已知题目的题意：每个数组中的元素不会超过 100，数组的⼤⼩不会超过 200。
而总和不会⼤于20000，背包最⼤只需要其中⼀半，所以10001⼤⼩就可以了。
vector dp(10001, 0);
4.确定遍历顺序
如果使⽤⼀维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒叙遍历！
（如果使用一维，必须先遍历物品后遍历背包容量，不可以反过来。因为如果反过来，就无法使用压缩数组的核心思想：《使用上一行作为结果》）
- // 开始 01背包
- for(int i = 0; i < nums.size(); i++) {
- for(int j = target; j >= nums[i]; j--) {
- // 每⼀个元素⼀定是不可重复放⼊，所以从⼤到⼩遍历
- dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- }
- }
5. 举例推导dp数组 dp[i]的数值⼀定是⼩于等于i的。
如果dp[i] == i 说明，集合中的⼦集总和正好可以凑成总和i，理解这⼀点很重要。
这也是本题能使用背包算法的核心要点和难点！
最终代码如下：
二维版：
- class Solution {
- public:
- bool canPartition(vector<int>& nums) {
- int sum=0;
- int maxNum=INT_MIN;
- for(int i=0;i<nums.size();i++){
- sum+=nums[i];
- maxNum=max(maxNum,nums[i]);
- }
- int len=nums.size();
- int target=sum/2;
- sum/=2;
- if(sum%2!=0)return false;
- if(maxNum>target)return false;
- vector<vector<int>> dp(len,vector<int> (target+1));
-
- for(int j=1;j<=target;j++){
- if(j-nums[0]>=0)dp[0][j]=nums[0];
- }
-
- for(int i=1;i<=len-1;i++){
- for(int j=1;j<=sum;j++){
- if(j-nums[i]>=0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
- else dp[i][j]=dp[i-1][j];
- }
- }
- return dp[len-1][sum]==sum;
-
- }
- };
一维版：
- class Solution {
- public:
- bool canPartition(vector<int>& nums) {
- int sum=0;
- int maxNum=INT_MIN;
- for(int i=0;i<nums.size();i++){
- sum+=nums[i];
- maxNum=max(maxNum,nums[i]);
- }
- int len=nums.size();
- int target=sum/2;
- if(sum%2!=0)return false;
-
- sum/=2;
- if(maxNum>target)return false;
- vector<int> dp(target+1) ;
-
- for(int j=1;j<=target;j++){
- if(j-nums[0]>=0)dp[j]=nums[0];
- }
-
- for(int i=1;i<=len-1;i++){
- for(int j=sum;j>=0;j--){
- if(j-nums[i]>=0)dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
- else dp[j]=dp[j];
- }
- }
- return dp[sum]==sum;
-
- }
- };
1049.最后一块石头的重量
这题怎么用动态规划，怎么用背包呢？
乍一看好像没什么思路，先来实际跟着例子手操试一下要怎么做。
stones = [2,7,4,1,8,1]
假如我们用最普通的顺序，我们依次让前两个石头碰一碰。
例如2和7碰，得到5，然后5和4碰，得到1，然后1和1碰，就变成0了，最后剩下8和1，那得到7。
很明显可以看到，这个留下的数字是比较大的，那我们要怎么做才能让最终留下的数字变小呢？
回顾上面刚才的过程中，在碰到一半的过程中，出现了
stones = [1,1,8,1]的过程
那我们要怎么做才可以使得最终结果最小呢？
我们不应该让前两个1自己碰，这属于是内耗，我们应该让三个弱小的1联手起来去攻打大的8！
换言之，我们想让最终得到的结果最小，我们应该将整个石头划分为势力接近均等的两个势力，如果出现一方势力强于另一方势力很多，那么最终赢的那方剩下的兵力就比较强。
而划分为接近均等的两股势力这就和之前的分割等和子集很像了!
所以此处才可以使用背包问题，核心思想就是尽可能凑到接近sum/2的水平。
那么分析和步骤和之前类似，容量为sum/2，
⽽我们要求的target其实只是最⼤重量的⼀半，所以dp数组开到15000⼤⼩就可以了。 当然也可以把⽯头遍历⼀遍，计算出⽯头总重量 然后除2，得到dp数组的⼤⼩。 我这⾥就直接⽤15000了。
vector dp(15001, 0);
最终代码如下：
二维版：
- class Solution {
- public:
- int lastStoneWeightII(vector<int>& stones) {
- int len=stones.size();
- int sum=0;
- for(auto val:stones){sum+=val;}
- int target=sum/2;
- vector< vector<int> > dp(len,vector<int>(target+1));
- for(int j=1;j<=target;j++){
- if(j>=stones[0])dp[0][j]=stones[0];
- }
-
- for(int i=1;i<len;i++){
- for(int j=1;j<=target;j++){
- if(j>=stones[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
- else dp[i][j]=dp[i-1][j];
- }
- }
- return sum-dp[len-1][target]-dp[len-1][target];
- }
- };
一维版：
- class Solution {
- public:
- int lastStoneWeightII(vector<int>& stones) {
- int len=stones.size();
- int sum=0;
- for(auto val:stones){sum+=val;}
- int target=sum/2;
- vector<int> dp(target+1);
- for(int j=1;j<=target;j++){
- if(j>=stones[0])dp[j]=stones[0];
- }
-
- for(int i=1;i<len;i++){
- for(int j=target;j>=0;j--){
- if(j>=stones[i])dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
- else dp[j]=dp[j];
- }
- }
- return sum-dp[target]-dp[target];
- }
- };
494.目标和
本题可以使用回溯法，后续再考虑。
- 如何转化为01背包问题呢。
首先每个数字只能选一次，我们选择它是正还是负。
那么最终我们要解出哪些是正的哪些是负的，正的减去负的得到就是我们target。
假设加法项的总和为positive，那么减法项的绝对值对应的总和设为negative
于是有：
positive+negative=sum;
positive-negative=target;
则positive=（target+sum）/2
所以如果给出了target，我们就可以算出来positive。
那有了positive后，我们要做的是就算出我们哪些项可以凑出positive，于是又回归到了背包问题，只不过此时的目标和不是target，而是positive。
不过有个地方需要注意，就是x=（target+sum）/2可能会发生溢出的问题，以及向下取整会不会产生问题。
首先看数据，可知本题不会溢出：
- 再看什么时候会发生向下取整，如何应对？
假如sum为5，而target为2，那么此时会发生向下取整。
但是我们仔细思考可以发现，如果sum为5，无论是1和4，还是2和3，都无法凑出target为2的情况。
事实上分析后可以得知，当sum和target的和不为偶数时，怎么都凑不出来target。所以此种情况我们可以直接返回0，即凑不出答案。
- 然后本题属于背包问题中的哪一种呢？
是01背包问题，为什么是01背包呢？ 因为每个物品（题⽬中的1）只⽤⼀次
- 至于这个递推公式要怎么计算呢？
这次和之前遇到的背包问题不⼀样了，之前都是求容量为j的背包，最多能装多少。 本题则是装满有⼏种⽅法。其实这就是⼀个组合问题了
动规五步曲
1. 确定dp数组以及下标的含义
dp[j] 表示：填满j（包括j）这么⼤容积的包，有dp[i]种⽅法。
其实也可以使⽤⼆维dp数组来求解本题，dp[i][j]：使⽤ 下标为[0, i]的nums[i]能够凑满j（包括j）这么⼤ 容量的包，有dp[i][j]种⽅法。
下⾯统⼀使⽤⼀维数组进⾏讲解， ⼆维降为⼀维（滚动数组），其实就是上⼀层拷⻉下来。
2. 确定递推公式
回顾一下以前使用背包问题时的递推公式都是，
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
代表选择或者不选择当前物品所能得到的最大价值。
如果不选择当前物品，则直接由上面一行继承，如果选择该物品，则计算减去当前物品的体积后，剩余的体积所能获得的最大价值，再加上当前物品的价值。
对于本题，我们先来举例子判断一下。
其中sum为5，target为3，则目标的x为（5+3）/2=4。
然后我们的目标就是在上面的5个数字中，每个数字有选与不选两种选择，然后凑出4来。与01背包问题不同的在于我们要求出有多少种解法。
比如第0行（代表只使用第0个物品），当j为0时，dp[i][j]为1，因为此时不选择即可使得和为0。
第0行，j为1时，dp[i][j]也为1，因为此时选择即可使得和为1。至于第一行后面的数都为0了，因为不可能凑出和为2、3、4的情况。故初始化如下：
本题的dp[i][j]就代表已经使用了前i件物品的情况下，凑出价值为j的物品有多少种。
而对于第1个物品，和为0的情况，此时是没得选择的，所有的物品都应该不选择，所以只有一种解法。对于第2、3、4、5个物品是同理的。
所以最终初始化如下：
对于使用第一个物品，target为1的情况，此时就有两种选择，对于当前物品的选与不选：
如果不选择当前物品，则继承上一行，即有dp[i-1][j]种选择
如果选择当前物品，则有dp[i-1][j-nums[i]]种选择。
两种情况加起来则有dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]种选择。
此即为递推公式。
如果使用的是一维数组，那么此时dp[i][j]就等于dp[i-1][j]了，于是不需要再加上上一行的自己，那么只需要再加上dp[i-1][j-nums[i]]即可。
于是一维的递推公式：
dp[j]+=dp[j-nums[i]]；
所以最终代码如下：
个人书写版：
以下代码有几个注意的点，与传统背包问题不同，本题是计算方法数。以前背包问题遍历的行数，就是物品的数量，比如物品有4个，则行数从是，0，1，2，3，
但是题是计算“能够凑满该容量的方法数，也就是说，也可以不选该物品，那么假如物品有4个，则行数就是0，1，2，3，4，有5行！
- class Solution {
- public:
- int findTargetSumWays(vector<int>& nums, int target) {
- int positive,negative;
- int sum=0;
- int len=nums.size();
- for(int i=0;i<len;i++){
- if(nums[i]<0)nums[i]=-nums[i];
- sum+=nums[i];
- }
- //if(abs(target)>sum)return 0;
- if(target<0)target*=-1;
- //positive+negative=sum;
- //positive-negative=target;
- if(target>sum)return 0;
- if((sum+target)%2!=0)return 0;
- positive=(sum+target)/2;
- vector< vector<int> > dp(len+1,vector<int>(15000));
-
- dp[0][0]=1;
- //dp[0][nums[0]]=1;
- /*for(int j=0;j<=positive;j++){
- if(j>=nums[0])dp[0][j]=nums[0];
- }由于是计算凑满的方法数，而不是计算该容量能存放多少东西，因此第一行只有一个数不为0，这与以往的初始化第一行的方法不同*/
-
-
- for(int i=1;i<=len;i++){
- for(int j=0;j<=positive;j++){
- dp[i][j]=dp[i-1][j];
- if(j>=nums[i-1])dp[i][j]+=dp[i-1][j-nums[i-1]];
- }
- }
-
-
-
- return dp[len][positive];
-
- }
- };
另外还有一点，本题由于会出数组中有负值，或者target为负值，但是事实上无论正负不会影响方法数，而负数有时候不方便计算，所以可以全部转化为正数，如图中这样：
一维版如下：
- class Solution {
- public:
- int findTargetSumWays(vector<int>& nums, int target) {
- int positive,negative;
- int sum=0;
- int len=nums.size();
- for(int i=0;i<len;i++){
- if(nums[i]<0)nums[i]=-nums[i];
- sum+=nums[i];
- }
- //if(abs(target)>sum)return 0;
- if(target<0)target*=-1;
- //positive+negative=sum;
- //positive-negative=target;
- if(target>sum)return 0;
- if((sum+target)%2!=0)return 0;
- positive=(sum+target)/2;
- vector<int> dp(15000);
-
- dp[0]=1;
- //dp[0][nums[0]]=1;
- /*for(int j=0;j<=positive;j++){
- if(j>=nums[0])dp[0][j]=nums[0];
- }由于是计算凑满的方法数，而不是计算该容量能存放多少东西，因此第一行只有一个数不为0，这与以往的初始化第一行的方法不同*/
-
-
- for(int i=1;i<=len;i++){
- for(int j=positive;j>=0;j--){
- dp[j]=dp[j];
- if(j>=nums[i-1])dp[j]+=dp[j-nums[i-1]];
- }
- }
-
-
-
- return dp[positive];
-
- }
- };
讲义版代码：
- class Solution {
- public:
- int findTargetSumWays(vector<int>& nums, int S) {
- int sum = 0;
- for (int i = 0; i < nums.size(); i++) sum += nums[i];
- if (abs(S) > sum) return 0; // 此时没有方案
- if ((S + sum) % 2 == 1) return 0; // 此时没有方案
- int bagSize = (S + sum) / 2;
- vector<int> dp(bagSize + 1, 0);
- dp[0] = 1;
- for (int i = 0; i < nums.size(); i++) {
- for (int j = bagSize; j >= nums[i]; j--) {
- dp[j] += dp[j - nums[i]];
- }
- }
- return dp[bagSize];
- }
- };
于是同理，力扣39：
假如本题不是要我们求满足target的具体组合，而是要求有多少种，就可以使用动态规划。
474.一和零
这道题和经典的背包问题非常相似，但是和经典的背包问题只有一种容量不同，这道题有两种容量，即选取的字符串子集中的 0 和 1的数量上限。
而且本题要求的是在限制了0和1的数量的情况下（也是相当于限定容量），问子集的个数最多可以为多少个。
以往的背包问题是限定容量的情况，该容量的商品最多值多少钱。而本题相当于限定容量后，最多能装多少个物品，物品数量越多相当于价值越大。
经典的背包问题可以使用二维动态规划求解，两个维度分别是物品和容量。这道题有两种容量，因此需要使用三维动态规划求解，三个维度分别是字符串、0的容量和 1 的容量。
完整版：
- class Solution {
- public:
-
- vector<int> getZeroOne(string &str){
- int len=str.size();
- vector<int> zeroOnes(2);
- for(int i=0;i<len;i++){
- zeroOnes[str[i]-'0']++;
- }
- return zeroOnes;
- }
- int findMaxForm(vector<string>& strs, int m, int n) {
- int len=strs.size();
- vector<vector<vector<int>>> dp(len,vector<vector<int>> (m+1,vector<int>(n+1)));
- vector<int> zeroOnes=getZeroOne(strs[0]);
- for(int j=0;j<=m;j++){
- for(int k=0;k<=n;k++){
- if(j>=zeroOnes[0]&&k>=zeroOnes[1])
- dp[0][j][k]=1;
- }
- }
-
- for(int i=1;i<len;i++){
- vector<int> zeroOnes=getZeroOne(strs[i]);
- int zeroNum=zeroOnes[0];
- int oneNum=zeroOnes[1];
- for(int j=0;j<=m;j++){
- for(int k=0;k<=n;k++){
- if(j>=zeroNum&&k>=oneNum)
- dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
- else
- dp[i][j][k]=dp[i-1][j][k];
- }
- }
- }
- return dp[len-1][m][n];
-
- }
- };
第0行是我自己多做了一步初始化的过程，
事实上，也可以多声明一行，然后从第一行开始遍历，然后就可以省去额外初始化的过程：
- class Solution {
- public:
- vector<int> getZeroOne(string &str){
- int len=str.size();
- vector<int> zeroOnes(2);
- for(int i=0;i<len;i++){
- zeroOnes[str[i]-'0']++;
- }
- return zeroOnes;
- }
-
- int findMaxForm(vector<string>& strs, int m, int n) {
- int len=strs.size();
- vector<vector<vector<int>>> dp(len+1,vector<vector<int>> (m+1,vector<int>(n+1)));
- for(int i=1;i<=len;i++){
- vector<int> zeroOnes=getZeroOne(strs[i-1]);
- int zeroNum=zeroOnes[0];
- int oneNum=zeroOnes[1];
- for(int j=0;j<=m;j++){
- for(int k=0;k<=n;k++){
- if(j>=zeroNum&&k>=oneNum)
- dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
- else
- dp[i][j][k]=dp[i-1][j][k];
- }
- }
- }
- return dp[len][m][n];
-
- }
- };
再简化一步，删去一个维度：
- class Solution {
- public:
- vector<int> getZeroOne(string &str){
- int len=str.size();
- vector<int> zeroOnes(2);
- for(int i=0;i<len;i++){
- zeroOnes[str[i]-'0']++;
- }
- return zeroOnes;
- }
-
- int findMaxForm(vector<string>& strs, int m, int n) {
- int len=strs.size();
- vector<vector<int>> dp(m+1,vector<int>(n+1));
- for(int i=1;i<=len;i++){
- vector<int> zeroOnes=getZeroOne(strs[i-1]);
- int zeroNum=zeroOnes[0];
- int oneNum=zeroOnes[1];
- for(int j=m;j>=0;j--){
- for(int k=n;k>=0;k--){
- if(j>=zeroNum&&k>=oneNum)
- dp[j][k]=max(dp[j][k],dp[j-zeroNum][k-oneNum]+1);
- else
- dp[j][k]=dp[j][k];
- }
- }
- }
- return dp[m][n];
-
- }
- };
完全背包
理论基础
对于这种题，一种简单的方法就是，比如对于背包来说最多装5件A物品，那么此时我们可以认为数组中有五件A物品，也就是说不是无限的。对每个物品都进行这样的操作，这样就可以将完全背包转化为01背包了。
接下来讲解通法，可以先从一般的例子入手，对比01背包的转移方程，我们可知，对于完全背包来说，其转移方程如下：
- dp[i,j]=max(dp[i-1,j] , dp[i-1,j-weight[i]]+value[i] , dp[i-1,j-2*weight[i]]+2*value[i] , dp[i-1,j-3*weight[i]]+3*value[i],.....
- ,dp[i-1,j-k*weight[i]]+k*value[i]
可以看到其有无穷多种。
那么这里怎么优化这个公式呢？
数学推导的方式可以见：完全背包 —— 打破思维定式 - 知乎 (zhihu.com)
对于完全背包来说，最终的公式是这个：
好像和01背包没什么差别，对吧？其实差别在这里！第二项取得是i而不是i-1。
如何理解呢？完全背包重点在于一件物品可以取多次。在原来的01背包中，第二项用的是dp[i-1][j-w[i]]，代表的是用上一行，也就是上一个物品的数据。
而为什么这里用的是dp[i][j-w[i]]呢？为什么是第i行呢？首先对于动态规划的二维表格来说，第i行时代表的是第i个物品。而第i个物品我们希望可以使用多次，也就是说假如这一行前面使用过了第i件物品，而后面我们希望还可以使用，并且我们希望接下来是基于前面使用过了第i件物品的情况下的最大利益，后续可以继续添加第i件物品，所以此时我们就是以当前这行来计算后续的最大利益。
因而是第i行。
结论：完全背包相比01背包只需将原来动规中的状态转移方程变更一处，将i-1变为i即可，如下所示。
而对于压缩过后的一维数组来说，首先在回顾⼀下01背包的核⼼代码
- 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]);
- }
- }
01背包中如果从前往后遍历，因为只有一行，所以一行里前面修改的数据会影响后面的修改的数据，所以我们从后往前遍历。
而在完全背包中，我们希望前面修改的数据会影响后面修改的数据，所以只需要把遍历顺序改为从前往后即可！
- // 先遍历物品，再遍历背包
- 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]);
- }
- }
01背包中内外循环的顺序能否颠倒？
答：可以颠倒。
另一方面在完全背包中，对于⼀维dp数组来说，其实两个for循环嵌套顺序同样⽆所谓！ 因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可 以了。 遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
完全背包示例代码：
先遍历物品，再遍历背包容量
- // 先遍历物品，在遍历背包
- void test_CompletePack() {
- vector<int> weight = {1, 3, 4};
- vector<int> value = {15, 20, 30};
- int bagWeight = 4;
- vector<int> dp(bagWeight + 1, 0);
- 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]);
- }
- }
- cout << dp[bagWeight] << endl;
- }
- int main() {
- test_CompletePack();
- }
先遍历背包容量，再遍历物品：
-
- // 先遍历背包，再遍历物品
- void test_CompletePack() {
- vector<int> weight = {1, 3, 4};
- vector<int> value = {15, 20, 30};
- int bagWeight = 4;
-
- vector<int> dp(bagWeight + 1, 0);
-
- 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 << dp[bagWeight] << endl;
- }
- int main() {
- test_CompletePack();
- }
看似内外循环顺序可以颠倒，但那是对于纯完全背包才这样。但如果是变种问题，则顺序会有影响！
常见的背包问题有1、组合问题。2、True、False问题。3、最大最小问题。
分为三类。
希望用一种规律搞定背包问题 - 组合总和 Ⅳ - 力扣（LeetCode）
1、组合问题：
377. 组合总和 Ⅳ
494. 目标和
518. 零钱兑换 II
2、True、False问题：
139. 单词拆分
416. 分割等和子集
3、最大最小问题：
474. 一和零
322. 零钱兑换
518.零钱兑换 Ⅱ
但本题和纯完全背包不⼀样，纯完全背包是能否凑成总⾦额，⽽本题是要求凑成总⾦额的个数！
注意题⽬描述中是凑成总⾦额的硬币组合数，为什么强调是组合数呢？
例如示例⼀： 5 = 2 + 2 + 1
5 = 2 + 1 + 2 这是⼀种组合，都是 2 2 1。
这是⼀种组合，都是 2 2 1。 如果问的是排列数，那么上⾯就是两种排列了。 组合不强调元素之间的顺序，排列强调元素之间的顺序。
本题可以使用背包，我们要凑的金额数量就是容量，而不同价值的货币就是不同类型的商品。
而每个货币的币值，即代表重量，也代表价值。
本题与传统背包还有一个区别在于，要计算的是总方案数，而不是容量下的最大商品。因此动态规划方程如下：
回顾在非完全背包中，涉及到组合总数的dp递推公式如下（详情见494目标和）：
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]
而我们上面讨论过，由于是完全背包，所以只需要改动一个地方即可：
在递推的过程中，如果取的是第i-1行，说明不希望当前行对后续那行产生影响，如果取的是第i行，则说明希望这一行前面的结果对后面产生影响。
本题二维版完整代码：
- class Solution {
- public:
- int change(int amount, vector<int>& coins) {
- int len=coins.size();
- vector<vector<int> > dp(len+1,vector<int> (amount+1));
- dp[0][0]=1;留空一个第0行，这个第0行代表不使用任何物品。不使用任何物品的情况下凑出0的组合数为1，所以dp[0][0]=1。
- for(int i=1;i<=len;i++){ i从1开始
- for(int j=0;j<=amount;j++){ 但是容量是从0开始的，不像i从1开始
- if(j-coins[i-1]>=0)dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
- else dp[i][j]=dp[i-1][j];
-
- cout<<dp[i][j]<<" ";//打印有助于调试
- }
- cout<<endl;
- }
- return dp[len][amount];
- }
- };
注意，如果j这个容量值小于当前物品的价值时，要继承上一行的结果，红框这一行是不能漏掉的
如果是一维版的，先回顾一下一维版中的组合数的公式。
事实上，一维数组和二维最大的区别在于：一维不需要像二维那样继承上一行的值。
因为每个物品只使用一次，所以j的遍历是从后往前的，
而回到本题，因为希望dp数组中的同一行中，前面的对后面产生影响，因此j的遍历是从前往后
改遍历顺序后如下：
- class Solution {
- public:
- int change(int amount, vector<int>& coins) {
- int len=coins.size();
- vector<int> dp(amount+1);
- dp[0]=1;
- for(int i=1;i<=len;i++){
- for(int j=0;j<=amount;j++){
- if(j-coins[i-1]>=0)dp[j]+=dp[j-coins[i-1]];
- }
- }
- return dp[amount];
- }
- };
当然本题也可以有其他更简单的思路做法，就是既然物品可以使用很多次，那我就使用一次，使用两次，使用三次，……就摁算就行了
上面使用硬币的方式如下，比方说，5可以由5个1组成，此时为1种方式，假如有某个硬币币值为2，那么我们可以用2去替换其中的两个1，那么就变成2 1 1 1。于是方法就多了dp[3] 种，即：“组成2的方法加上组成3的方法。” 而组成2的方法就是一个货币，所以是一种。
所以即dp[5]+=dp[5-2];
而我们可以不止一次用2去替换两个1，可以替换两次，所以即2 2 1
所以答案即为：dp[5]+=dp[5-2*2];
也就是说，每有一种方法可以满足和a+b=5的话，就加上它。而方法数量就是dp[b]。（其中a为多次使用硬币，而b为5-a）
因而代码如下：
- class Solution {
- public int change(int cnt, int[] cs) {
- int n = cs.length;
- int[][] f = new int[n + 1][cnt + 1];
- f[0][0] = 1;
- for (int i = 1; i <= n; i++) {
- int val = cs[i - 1];
- for (int j = 0; j <= cnt; j++) {
- f[i][j] = f[i - 1][j];
- 初始时该行值为0，所以使用上一行来进行初始化，代表使用了上一轮的货币后，现在有多少种方法
- for (int k = 1; k * val <= j; k++) {
- f[i][j] += f[i - 1][j - k * val];
- }
- }
- }
- return f[n][cnt];
- }
- }
补充：上面的做法会出现不同的排列吗？比如说1 1 2本质和1 2 1是相同的，这两种顺序应该只记录一种。
答案是不会。
只会出现1 1 2 不可能出现 1 2 1。
原因如下：
当固定物品的时候（物品在外层循环），遍历背包容量的时候，dp 记录的是当前元素及以前的排列，不包含后面元素的排列，例如在固定元素为 1 时，遍历结束背包容量的时候，dp 记录的是只有元素 1 的时候，背包从空到满的排列方式。
当元素为 2 的时候，此时元素1在前一轮循环已经固定下来了。i=2时，准备固定的元素是2， ，i从2不断变大，没法变小，所以没办法查找 dp[i-元素1] 的情况，即 {元素2， 元素1} 这种排列方式漏掉了，只保留了{元素1，元素2}这种排列方式。
377.组合总和 Ⅳ（排列数）
注意，本题与39题：组合总和几乎一样：
区别在于39题需要返回具体的组合，那么就只能使用回溯法。
本题是只需要求数量，虽然可以用回溯，但是回溯的速度慢。因为只需要求数量，所以使用动规即可。
根据本题所给的顺序中：如果顺序不同也视为不同的组合，这与上面找零那题就区别开来了。上面找零中不允许重复。
dp[0]=1的意思就是，不选任何数字凑出0的方法就是1种。
当target（容量）放在外层循环时，而物品在内层循环时，对于每个dp[i][j]值，其会将所有物品再遍历一遍，那么这就可以出现将j值（比如等于4）分为【1+dp[3]】和【3+dp[1]】的情况
为什么在外层循环，就可以出现不同的组合呢？
定义dp[j]表示和为j的组合个数，那么这个dp[j]怎么求呢。举个例子，比如j是5，如果要找和为5的组合，
我们可以用和为1的组合加上一个4
或者用和为2的组合加上3
或者用和为3的组合加上2
或者用和为4的组合加上1
而和为1，2，3，4的组合个数分别是dp[1]，dp[2]，dp[3]，dp[4]。
所以和为5的组合个数就是他们几个的和，也就是dp[5]=dp[1]+dp[2]+dp[3]+dp[4];
这个j就代表着容量，并且是一维数组，按照上面所想的，写出了下面的代码：
- class Solution {
- public:
- int combinationSum4(vector<int>& nums, int target) {
- int len=nums.size();
- vector<vector<unsigned long long>> dp(len+1,vector<unsigned long long > (target+1));
- dp[0][0]=1;
- for(int j=0;j<=target;j++){
- for(int i=1;i<=len;i++){
- dp[i][j]=dp[i-1][j];
- if(j>=nums[i-1])dp[i][j]+=dp[i][j-nums[i-1]];
- }
- }
- return dp[len][target];
- }
- };
-
但是发现不对，这是为什么呢？
回想下前面，当我们想使用
遍历顺序是一列一列从左往右的遍历，比如对于容量1，去遍历完0~4的物品，此时就知道了dp[1]的大小是什么，在二维数组中，这个dp[1]其实就是dp[len][1]
因此，本文真正的遍历二维的代码如下：
- class Solution {
- public:
- int combinationSum4(vector<int>& nums, int target) {
- int len=nums.size();
- vector<vector<unsigned long long>> dp(len+1,vector<unsigned long long > (target+1));
- dp[0][0]=1;
- for(int j=0;j<=target;j++){
- for(int i=1;i<=len;i++){
- dp[i][j]=dp[i-1][j];
- if(j>=nums[i-1])dp[i][j]+=dp[len][j-nums[i-1]];
- }
- }
- return dp[len][target];
- }
- };
-
对比上文仅改动了这样的一个地方：
这样才能实现充分利用《前面对于每一个固定的容量j都去遍历了从0到i的所有物品后得到的该容量有多少种情况》的这个结果
转化到一维的情况下时，此时
因此最终代码如下：只需要改动几个地方即可
- class Solution {
- public:
- int combinationSum4(vector<int>& nums, int target) {
- int len=nums.size();
- vector<unsigned long long> dp(target+1);
- dp[0]=1;
- for(int j=0;j<=target;j++){
- for(int i=1;i<=len;i++){
- if(j>=nums[i-1])dp[j]+=dp[j-nums[i-1]];
- }
- }
- return dp[target];
- }
- };
-
注意到本题中有很大的数据，加和后可能会导致溢出，所以使用unsigned long long型。
由于是一维的，所以行数不需要像二维的那样自己多弄出一个第一行来做特殊处理，所以代码可以再优化一下变成下面这种：
- class Solution {
-
- public:
-
- int combinationSum4(vector<int>& nums, int target) {
-
- int len=nums.size();
-
- vector<unsigned long long> dp(target+1);
-
- dp[0]=1;
-
- for(int j=0;j<=target;j++){
-
- for(int i=0;i<len;i++){
-
- if(j>=nums[i])dp[j]+=dp[j-nums[i]];
-
- }
-
- }
-
- return dp[target];
-
- }
-
- };
70.爬楼梯（n阶，完全背包解法）
注意，此时的容量是n，即总共的台阶数，物品即为跳的步骤数目：
322.零钱兑换
518题是求方法数，而本题是求最小数，核心模型都是背包模型，区别在于本题使用的递归方程是求最大最小值类型的。本题和原始背包一样，原始背包问题求的是最大价值，而本题求的是最小数量。都是求一个最大值，只不过原始背包问题的价值是有一个独特的value数组来衡量的，而本题的最小个数，可以直接衡量。
初始化因为是要找能凑出的最小的数，所以那些凑不出的dp值应该设为一个很大的数
为了防止INT_MAX+1之后溢出，可以使用long型来存储
另一方面，假如当前格子的容量不足以装新东西，那么方案数至少是上一层的内容
-
-
- class Solution {
- public:
- int coinChange(vector<int>& coins, int amount) {
- if(amount==0)return 0;
- int len=coins.size();
- vector<vector<long>> dp(len+1,vector<long> (amount+1,INT_MAX));
- dp[0][0]=0;
-
- for(int i=1;i<=len;i++){
- for(int j=0;j<=amount;j++){
- if(j>=coins[i-1])dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
- else dp[i][j]=dp[i-1][j];
- }
- }
- if(dp[len][amount]>=INT_MAX)return -1;
- return dp[len][amount];
- }
- };
再将其改造成一维的就变成了：
- class Solution {
- public:
- int coinChange(vector<int>& coins, int amount) {
- if(amount==0)return 0;
- int len=coins.size();
- vector<long> dp(amount+1,INT_MAX);
- dp[0]=0;
-
- for(int i=0;i<len;i++){
- for(int j=0;j<=amount;j++){
- if(j>=coins[i])dp[j]=min(dp[j],dp[j-coins[i]]+1);
- }
- }
- if(dp[amount]>=INT_MAX)return -1;
- return dp[amount];
- }
- };
279.完全平方数
4.确定遍历顺序
本题的遍历顺序没有要求，因为此处不对组合数还是排列数做要求。
但是此处最好用背包容量在外，物品在内。
因为其实物品有无数种，但是要求是物品的²要小于容量，那么可以先确定容量，然后让j从1到根号容量，逐渐变大的循环。
- class Solution {
- public:
- int numSquares(int n) {
- vector<int> dp(n+1,INT_MAX);
- dp[0]=0;
- for(int i=1;i<=n;i++){
- for(int j=1;j*j<=i;j++){
- dp[i]=min(dp[i],dp[i-j*j]+1);
- }
- }
- return dp[n];
- }
- };
当然物品数量在外也可以，只不过就要稍微注意一下条件了：
- class Solution {
- public:
- int numSquares(int n) {
-
- vector<long> dp(n+1,INT_MAX);
- dp[0]=0;
- int j=1;
- for(int i=1;i*i<=j;i++){
- for(j=1;j<=n;j++){
- if(j>=i*i)dp[j]=min(dp[j],dp[j-i*i]+1);
- }
- }
-
-
- return dp[n];
- }
- };
139.单词拆分
这题我个人感觉和背包关系不大…
自己需要初始化第一个格子的位置，可以用dp0表示，意思是空字符串在字典中一定可以找到，即的 拼接一定为true，
背包问题总结篇
⼆维dp数组01背包先遍历物品还是先遍历背 包都是可以的，且第⼆层for循环是从⼩到⼤遍历。
⼀维dp数组01背包只能先遍 历物品再遍历背包容量，且第⼆层for循环是从⼤到⼩遍历。
