【动态规划七】背包问题

目录

0/1背包问题

一、【模板】01背包

二、分割等和子集

三、目标和

四、最后一块石头的重量 II

完全背包问题

一、【模板】完全背包

二、零钱兑换

三、零钱兑换 II

四、完全平方数

二维费用的背包问题

一、一和零

二、盈利计划

似包非包

组合总和

卡特兰数

不同的二叉搜索树

背包问题:

有1个背包，地上一堆物品，挑选一些物品放入背包中

问：能挑选物品的最大的价值是多少?

两个限制:

1.物品的属性(比如物品的体积，重量,  价值等)

2.背包的属性(背包的最大容量，承重等)

当物品的个数都限制为1个时，此时的背包问题就是0/1背包问题，因为每个物品选就是1个，不选就是0个

当物品的个数没有任何限制，都有无穷多个时，此时的背包问题就是完全背包问题

本篇博客介绍0/1背包问题

0/1背包问题

一、【模板】01背包

【模板】01背包_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=N7T8https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D1961.题目解析

两个问题:

1.能装的物品的最大价值是多少?(可以装满，也可以不装满)

2.要求恰好装满，此时物品的最大价值是多少?

2.算法分析

问题一:

1.状态表示

背包问题本质还是线性dp问题，所以状态表示依旧是 经验 + 题目要求

dp[i]: 从前i个物品中挑选，所有选法中，能挑选的最大价值(×)

因为考虑第i个物品要不要放入背包的时候，必须先知道当前背包的容量才行

dp[i][j]: 从前i个物品中挑选，总体积不超过j, 所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

物品的编号从1开始，因此给dp表添加一行一列

第一行表示从前0个物品中挑选, 体积不超过j，能挑选的最大价值, 全是0

第一列表示从前i个物品中挑选, 体积不超过0，能挑选的最大价值, 全是0

4.填表顺序

从上往下填表

5.返回值

dp[n][V]

问题二:

1.状态表示

dp[i][j]: 从前i个物品中挑选，总体积正好等于 j,  所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

物品的编号从1开始，因此给dp表添加一行一列

dp[0][0] 表示从前0个物品中挑选，体积恰好为0的最大价值，什么都不选即可，那就是0

第一行的其余位置:

从前0个物品中挑选，价值恰好为j(j > 0)的最大价值，由于0个物品，所以凑不出价值恰好为j，因此值都是-1

第一列的其余位置:

从前i个物品中挑选，体积恰好为 0 的最大价值，一个物品都不选即可, 所以都是0

4.填表顺序

从上往下填表

5.返回值

dp[n][V] == -1 ? 0 : dp[n][V]

3.算法代码

#include <iostream>
using namespace std;
#include <string.h>const int N = 1010;
int n, V, v[N], w[N]; //物品个数，背包体积，物品体积数组，物品价值数组
int dp[N][N];int main() 
{//读入数据cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];//第一问for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);}}cout << dp[n][V] << endl;//第二问memset(dp, 0, sizeof(dp)); //清空dp表for(int j = 1; j <= V; j++) //初始化dp表dp[0][j] = -1;for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j >= v[i] &&  dp[i-1][j-v[i]] != -1) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);}}cout << (dp[n][V] == -1 ? 0 : dp[n][V])  << endl;
}

四、空间优化

我们在最开始讲解动态规划时就提到过，背包问题中经常可以使用空间优化，也就是不必使用二维数组，根据状态转移方程， 填写dp[i][j]时，只需要dp[i-1][j]与dp[i-1][j-v[i]]的值，因此只需要两行即可，也就是两个一维数组即可

而我们可以i进一步优化，也就是只需要一个一维数组即可, 也就是用dp[i-1][j-v[i]]的值与dp[i-1][j]的值在原始数组上更新dp[i][j]即可, 不过要注意，由于在原始数组上更新，防止发生覆盖，需要从右向左更新, 而代码只需要把所有的二位数组的第一维全删掉，填表的第二层for循环从右向左填并且可以把更新状态转移方程的条件放在循环条件的判断处即可

#include <iostream>
using namespace std;
#include <string.h>const int N = 1010;
int n, V, v[N], w[N]; //物品个数，背包体积，物品体积数组，物品价值数组
int dp[N];int main() 
{//读入数据cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];//第一问for(int i = 1; i <= n; i++)for(int j = V; j >= v[i]; j--)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);cout << dp[V] << endl;//第二问memset(dp, 0, sizeof(dp)); //清空dp表for(int j = 1; j <= V; j++) //初始化dp表dp[j] = -1;for(int i = 1; i <= n; i++)for(int j = V; j >= v[i]; j--)if(dp[j-v[i]] != -1) dp[j] = max(dp[j], dp[j-v[i]] + w[i]);cout << (dp[V] == -1 ? 0 : dp[V])  << endl;
}

二、分割等和子集

416. 分割等和子集 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/partition-equal-subset-sum/1.题目解析

给定一个只包含正整数的数组，问是否可以将数组划分成元素和相等的两部分

2.算法分析

转化一下: 本质就是从数组中挑选一些数，看这些数之和能否等于sum/2即可

本题虽然不完全是0/1背包问题，但是可以划分到该0/1背包问题，因为每个数要么选，要么不选，相当于每个物品选或不选，而且本题比0/1背包问题更加简单，因为本题就是看数字能否凑成sum/2即可, 0/1背包问题求的是物品的价值和最大~

1.状态表示

dp[i][j]: 表示从前i个数中挑选，和能否凑成j

2.状态转移方程

3.初始化

添加有一行一列

dp[0][0] = true, 表示一个数都不选，是否可以凑成0， 当然可以

第一行的其余位置:  i =0, 表示一个数都不选，能否凑成1, 2, 3...., 当然不可以，值为false

第一列的其余位置:  j = 0, 表示从前i个数选，和能否凑成0, 一个都不选即可，值为true

4.填表顺序

从上往下填表

5.返回值

dp[n][sum/2]

3.算法代码

二维dp表:

class Solution {
public:bool canPartition(vector<int>& nums) {//求数组所有元素的和int sum = 0;for(auto x : nums)sum += x;if(sum % 2) return false; //和是奇数, 直接返回false//1.创建dp表int m = nums.size(), aim = sum / 2;vector<vector<bool>> dp(m+1, vector<bool>(aim+1));//2.初始化for(int i = 0; i <= m ;i++)dp[i][0] = true;//3.填表for(int i = 1; i <= m; i++){for(int j = 1; j <= aim; j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1]) //注意下标的映射关系dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];}}//4.返回值return dp[m][aim];}
};

滚动数组优化:

class Solution {
public:bool canPartition(vector<int>& nums) {//求数组所有元素的和int sum = 0;for(auto x : nums)sum += x;if(sum % 2) return false; //和是奇数, 直接返回false//1.创建dp表int m = nums.size(), aim = sum / 2;vector<bool> dp(aim+1);//2.初始化dp[0] = true;//3.填表for(int i = 1; i <= m; i++)for(int j = aim; j >= nums[i-1]; j--)dp[j] = dp[j] || dp[j-nums[i-1]];//4.返回值return dp[aim];}
};

三、目标和

494. 目标和 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/target-sum/1.题目解析

给定一个非负nums数组和整数target, 给每个数组元素前可以加正负号，使得最终表达式运算的结果 == target即可，求满足条件的表达式的数目

2.算法分析

题目本质就是将数组划分成一堆正数和负数，假如正数的和是a, 负数的和的绝对值是b, 那么a-b==target, 而我们知道a + b == sum, 消元得 a = (target + sum) / 2;

因此问题就转化成了在数组中挑一些数，使得这些数的和等于a, 问共有多少种选法?? 此时与题目二基本一样了， 仍然属于0/1背包问题

1.状态表示

dp[i][j]: 从前i个数中挑选，总和正好等于j, 一共有多少种选法

2.状态转移方程

3.初始化

添加一行一列

dp[0][0] = 1, 表示 从前 0个数中挑选，总和恰好为0, 只要一个数都不选即可

第一行的其余位置: 表示 从前 0个数中挑选，总和恰好为j(>0), 显然不可能，因此值都为0

第一列的其余位置: 表示 从前 i个数中挑选，总和恰好为0, 但是nums中的元素值可能为0，因此可能有很多选法，但实际上不用初始化，因为初始化是为了防止越界，而第一列j = 0, 如果要用dp[i-1][j-nums[i]]这个状态转移方程，必须满足j >= nums[i], 也就是nums[i]只能等于0，此时dp[i-1][j-nums[i]]就是 dp[i-1][0]了，也就是正上方的值，因此不会越界, 因此无需初始化

4.填表顺序

从上往下填表

5.返回值

dp[n][a]

3.算法代码

二维dp表:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(auto x : nums)sum += x;int a = (sum + target) / 2;if(a < 0 || (sum + target) % 2) return 0; //a小于0或者sum+target是奇数, 直接返回0//1.创建dp表int n = nums.size();vector<vector<int>> dp(n+1, vector<int>(a+1));//2.初始化dp[0][0] = 1;//3.填表for(int i = 1; i <= n; i++){for(int j = 0; j <= a; j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1])dp[i][j] += dp[i-1][j-nums[i-1]];}}//4.返回值return dp[n][a];}
};

滚动数组优化:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(auto x : nums)sum += x;int a = (sum + target) / 2;if(a < 0 || (sum + target) % 2) return 0; //a小于0或者sum+target是奇数, 直接返回0//1.创建dp表int n = nums.size();vector<int> dp(a+1);//2.初始化dp[0] = 1;//3.填表for(int i = 1; i <= n; i++)for(int j = a; j >= nums[i-1]; j--)dp[j] += dp[j-nums[i-1]];//4.返回值return dp[a];}
};

四、最后一块石头的重量 II

1049. 最后一块石头的重量 II - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/last-stone-weight-ii/description/1.题目解析

之前我们已经在<<优先级队列>>博客中讲解了"最后一块石头的重量 I", 每次选两块最重的石头，而本题每次随机选两个石头进行碰撞，如果最后还剩余了一块石头，那么求最终剩余石头的最小重量，如果没有剩余石头，那么返回0

2.算法分析

本题的难点仍然在于如何把原问题进行转化，假设给定的数组元素是[a, b, c, d, e]

每次随机选两个石头进行碰撞, 可以发现最终结果无非是给原始数组元素添加上正负号，使得最终

的结果最小即可, 而我们可以把数分成两堆，一堆是正数，一堆是负数，假设正数的和是a, 负数和的绝对值是b, 已知a + b == sum, 求a - b 的最小值(也可能是b-a), 而a - b要最小，也就是a/b要最接近 sum的一半，此时问题就变成了0/1背包问题

把每一个数看成一个物品，每个物品的体积和价值都是nums[i], 挑选一些物品，背包的容量为sum / 2, 问能够装的的最大价值

1.状态表示

dp[i][j]: 从前i个数选，总和不超过j, 此时的最大和

2.状态转移方程

3.初始化

添加一行一列

第一行表示从前0个物品中挑选, 体积不超过j，能挑选的最大价值, 全是0

第一列表示从前i个物品中挑选, 体积不超过0，能挑选的最大价值, 全是0

4.填表顺序

从上往下

5.返回值

dp[n][m]相当于 a, sum - dp[n][m]是b, 由于dp[n][m] <= sum / 2的， b - a 一定 >= 0,  因此返回 b - a 即 sum - 2 * dp[n][m]

3.算法代码
二维dp表:

class Solution {
public:int lastStoneWeightII(vector<int>& nums) {int n = nums.size();int sum = 0;for(auto x : nums)sum += x;int aim = sum / 2;//1.创建dp表vector<vector<int>> dp(n+1, vector<int>(aim+1));//2.填表for(int i = 1; i <= n; i++){for(int j = 1; j <= aim; j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1])dp[i][j] = max(dp[i][j], dp[i-1][j-nums[i-1]] + nums[i-1]);}}//3.返回值return sum - 2 * dp[n][aim];}
};

滚动数组优化:

class Solution {
public:int lastStoneWeightII(vector<int>& nums) {int n = nums.size();int sum = 0;for(auto x : nums)sum += x;int aim = sum / 2;//1.创建dp表vector<int> dp(aim+1);//2.填表for(int i = 1; i <= n; i++)for(int j = aim; j >= nums[i-1]; j--)dp[j] = max(dp[j], dp[j-nums[i-1]] + nums[i-1]);//3.返回值return sum - 2 * dp[aim];}
};

完全背包问题

一、【模板】完全背包

完全背包和0/1背包的区别就是完全背包问题中每个物品的个数是不限的

【模板】完全背包_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=N7T8https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D1961.题目解析

两个问题:

1.能装的物品的最大价值是多少?(可以装满，也可以不装满)

2.要求恰好装满，此时物品的最大价值是多少?

2.算法分析

问题一:

1.状态表示

dp[i][j]: 从前i个物品中挑选，总体积不超过j, 所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

添加一行一列

第一列不可能越界，因为第一列 j = 0, 而 dp[i][j-v[i]] + w[i] 是在 j >= v[i]的情况下成立的，因此v[i] 只能等于0, 因此不会越界。

第一行表示从前0个物品挑选，体积不超过 j的最大价值，全都初始化成0即可

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[n][V]

问题二:

1.状态表示

dp[i][j]: 从前i个物品中挑选，总体积正好等于j , 所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

添加一行一列

同理，第一列不可能越界

dp[0][0] 表示从前0个物品中挑选，体积恰好为0的最大价值，那就是0

第一行的其余位置: 从前0个物品中挑选，体积恰好为j(j>0)的最大价值，由于没有物品，所以体积不可能 > 0, 因此都是-1

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[n][V] == -1 ? 0 : dp[n][V]

3.算法代码

#include <iostream>
using namespace std;
#include <string.h>const int N = 1001;
int n, V, v[N], w[N];
int dp[N][N];int main() 
{cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i++){for(int j = 0; j <= V; j++){dp[i][j] = dp[i-1][j];if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);}}cout << dp[n][V] << endl;memset(dp, 0, sizeof(dp));for(int j = 1; j <= V; j++)dp[0][j] = -1;for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j >= v[i] && dp[i][j-v[i]] != -1)dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);}}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
}

4.空间优化

更新dp[i][j]会用到两个绿色格子的值，而空间优化的本质就是只用一个一维dp表

黄色表示还没更新的值，绿色表示已经更新过的值，因此要填dp[i][j], 必须要保证用到的两个格子已经变成了绿色格子才可以，因此必须从左往右填一维dp表!!  这也是和0/1背包空间优化不同的地方，0/1背包是从右往左填一维dp表的

#include <iostream>
using namespace std;
#include <string.h>const int N = 1001;
int n, V, v[N], w[N];
int dp[N];int main() 
{//输入cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];//问题一for(int i = 1; i <= n; i++)for(int j = v[i]; j <= V; j++)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);cout << dp[V] << endl;//问题二memset(dp, 0, sizeof(dp));for(int j = 1; j <= V; j++)dp[j] = -1;for(int i = 1; i <= n; i++)for(int j = v[i]; j <= V; j++)if(dp[j-v[i]] != -1)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
}

补充:

在问题二的代码中，用状态转移方程之前要先判断要用到的状态是否存在，事实上，我们也可以不用判断，只要保证求完max之后不会对结果产生影响即可，因此在初始化的时候，可以初始化成-0x3f3f3f3f即可

#include <iostream>
using namespace std;
#include <string.h>const int N = 1001;
int n, V, v[N], w[N];
int dp[N];int main() 
{//输入cin >> n >> V;for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];//问题一for(int i = 1; i <= n; i++)for(int j = v[i]; j <= V; j++)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);cout << dp[V] << endl;//问题二memset(dp, 0, sizeof(dp));for(int j = 1; j <= V; j++)dp[j] = -0x3f3f3f3f;for(int i = 1; i <= n; i++)for(int j = v[i]; j <= V; j++)dp[j] = max(dp[j], dp[j-v[i]] + w[i]);cout << (dp[V] < 0 ? 0 : dp[V]) << endl;
}

二、零钱兑换

322. 零钱兑换 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/coin-change/1.题目解析

给定整数数组coins和一个整数amount表示总金额，求凑成amount所需要的硬币最小个数

2.算法分析

1.状态表示

dp[i][j]: 从前 i 个硬币中挑选，总和正好等于 j, 所有选法中，最少的硬币个数

2.状态转移方程

3.初始化

dp[0][0] = 0

第一行其余位置: 0x3f3f3f3f (参考上一道题目的补充内容)

4.填表顺序

从上往下填表, 每一行从左往右

5.返回值

dp[n][amout] >= 0x3f3f3f3f ? -1 : dp[n][amount]

3.算法代码

二维dp表

class Solution {
public:int coinChange(vector<int>& coins, int amount){int n = coins.size();const int INF = 0x3f3f3f3f;vector<vector<int>> dp(n+1, vector<int>(amount+1));for(int j = 1; j <= amount; j++)dp[0][j] = INF;for(int i = 1; i <= n; i++){for(int j = 0; j <= amount; j++){dp[i][j] = dp[i-1][j];if(j >= coins[i-1])dp[i][j] = min(dp[i][j], dp[i][j-coins[i-1]] + 1);}}return dp[n][amount] >= INF ? -1 : dp[n][amount]; }
};

空间优化:

class Solution {
public:int coinChange(vector<int>& coins, int amount){int n = coins.size();const int INF = 0x3f3f3f3f;vector<int> dp(amount+1, INF);dp[0] = 0;for(int i = 1; i <= n; i++)for(int j = coins[i-1]; j <= amount; j++)dp[j] = min(dp[j], dp[j-coins[i-1]] + 1);return dp[amount] >= INF ? -1 : dp[amount]; }
};

三、零钱兑换 II

518. 零钱兑换 II - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/coin-change-ii/description/1.题目解析

本题求的是凑成 amount 的硬币的组合个数

2.算法分析

1.状态表示

dp[i][j]: 从前 i 个硬币中挑选，总和正好等于 j, 一共有多少种选法

2.状态转移方程

3.初始化

dp[0][0] = 1, 表示从前 0 个硬币中挑选，总和恰好为0的，共有1种选法(就是什么都不选)

第一行的其余位置初始化成0即可, 表示从前 0 个硬币中挑选，总和恰好为 j (>0)，共有0种选法

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[n][amount]

3.算法代码

二维dp表

class Solution
{
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<vector<int>> dp(n+1, vector<int>(amount+1));dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= amount; j++){dp[i][j] = dp[i-1][j];if(j >= coins[i-1])dp[i][j] += dp[i][j-coins[i-1]];}}return dp[n][amount];}
};

空间优化 

class Solution
{
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<int> dp(amount+1);dp[0] = 1;for(int i = 1; i <= n; i++)for(int j = coins[i-1]; j <= amount; j++)dp[j] += dp[j-coins[i-1]];return dp[amount];}
};

四、完全平方数

279. 完全平方数 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/perfect-squares/1.题目解析

给定一个数n,  返回和为n的完全平方数的最小数量

2.算法分析

转化成完全背包问题

1.状态表示

dp[i][j]: 从前 i 个完全平方数中挑选，总和正好等于 j, 所有选法中，最小的数量

2.状态转移方程

3.初始化

dp[0][0] = 0, 从前 0 个完全平方数中挑选，总和恰好等于 0，只需要0个完全平方数即可

第一行其余位置:

从前 0 个完全平方数中挑选，总和恰好等于 j( > 0)，显然做不到，初始化成为0x3f3f3f3f即可

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[根号下n][n]

3.算法代码

二维dp表

class Solution 
{
public:int numSquares(int n) {//1.创建dp表int m = sqrt(n);vector<vector<int>> dp(m+1, vector<int>(n+1));const int INF = 0x3f3f3f3f;//2.初始化for(int j = 1; j <= n; j++)dp[0][j] = INF;//3.填表for(int i = 1; i <= m; i++){for(int j = 0; j <= n; j++){dp[i][j] = dp[i-1][j];if(j >= i*i)  dp[i][j] = min(dp[i][j], dp[i][j-i*i] + 1);}} //4.返回值return dp[m][n];}
};

 空间优化 

class Solution 
{
public:int numSquares(int n) {//1.创建dp表int m = sqrt(n);vector<int> dp(n+1);const int INF = 0x3f3f3f3f;//2.初始化for(int j = 1; j <= n; j++)dp[j] = INF;//3.填表for(int i = 1; i <= m; i++)for(int j = i*i; j <= n; j++)dp[j] = min(dp[j], dp[j-i*i] + 1);//4.返回值return dp[n];}
};

二维费用的背包问题

一、一和零

474. 一和零 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/ones-and-zeroes/description/1.题目解析

给你一个二进制字符串数组 strs 和两个整数 m 和 n ，找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1

2.算法分析

本质就是在字符串数组中挑选一些字符串出来，需要满足两个条件(1和0的个数限制)， 这类问题就是二维费用的背包问题(也分为二维费用的0/1背包问题 和 二维费用的完全背包问题

1.状态表示
dp[i][j][k] 表示 从前 i 个字符串中挑选，字符0的个数不超过j, 字符1的个数不超过k, 所有的选法中，最大的长度

2.状态转移方程

3.初始化

当i=0, 表示从前 0 个字符串中挑选，字符0的个数不超过j, 字符1的个数不超过k, 没有字符串可选，因此长度就是0, 全部初始化成0即可

4.填表顺序

i从小到大即可

5.返回值

dp[len][m][n]

len表示字符串的长度

3.算法代码

三维dp表

class Solution {
public: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++){//统计当前字符串中0/1字符的个数int a = 0, b = 0;for(auto ch : strs[i-1])if(ch == '0') a++;else b++;for(int j = 0; j <= m; j++){for(int k = 0; k <= n; k++){dp[i][j][k] = dp[i-1][j][k];if(j >= a && k >= b)dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-a][k-b] + 1); }}}return dp[len][m][n];}
};

空间优化

class Solution {
public: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++){//统计当前字符串中0/1字符的个数int a = 0, b = 0;for(auto ch : strs[i-1])if(ch == '0') a++;else b++;for(int j = m; j >= a; j--)for(int k = n; k >= b; k--)dp[j][k] = max(dp[j][k], dp[j-a][k-b] + 1); }return dp[m][n];}
};

二、盈利计划

879. 盈利计划 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/profitable-schemes/1.题目解析

n表示员工人数, minProfit表示至少需要产生的利润，profit数组和group数组对应, 第i种工作需要group[i]个员工完成，会产生profit[i]的利润，现在问有多少种选择工作的方法，使得能够产生的利润>=minProfit

2.算法分析

本质是二维费用的0/1背包问题

1.状态表示

dp[i][j][k]: 从前i个工作中挑选，总人数不超过 j, 总利润至少为 k, 一共有多少种选法

2.状态转移方程

3.初始化

dp[0][j][0],  i = 0表示没有计划, 没有计划就没有利润，因此 k 也是0，此时什么都不选就满足条件，因此将dp[0][j][0]初始化成1

4.填表顺序

i从小到大即可

5.返回值

dp[len][n][m]

len是group数组或profit数组的长度

3.算法代码

三维dp表

class Solution {
public:int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) {const int MOD = 1e9 + 7;//1.创建dp表int len = g.size();vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(n+1, vector<int>(m+1)));//2.初始化dp表for(int j = 0; j <= n; j++)dp[0][j][0] = 1;//3.填表for(int i = 1; i <= len; i++){for(int j = 0; j <= n; j++){for(int k = 0; k <= m; k++){dp[i][j][k] += dp[i-1][j][k];if(j >= g[i-1])dp[i][j][k] += dp[i-1][j-g[i-1]][max(0, k-p[i-1])];dp[i][j][k] %= MOD;}}}//4.返回值return dp[len][n][m];}
};

空间优化

class Solution {
public:int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) {const int MOD = 1e9 + 7;//1.创建dp表int len = g.size();vector<vector<int>> dp(n+1, vector<int>(m+1));//2.初始化dp表for(int j = 0; j <= n; j++)dp[j][0] = 1;//3.填表for(int i = 1; i <= len; i++)for(int j = n; j >= g[i-1]; j--)for(int k = m; k >= 0; k--){dp[j][k] += dp[j-g[i-1]][max(0, k-p[i-1])];   dp[j][k] %= MOD;}//4.返回值return dp[n][m];}
};

似包非包

组合总和

377. 组合总和 Ⅳ - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/combination-sum-iv/description/1.题目解析

给定一个nums数组和target目标值，从nums数组中找出和为target的排列个数，每个数可以选择无数次，注意顺序不同算是不同的情况

2.算法分析

"背包问题"研究的本质是限制条件下的组合问题，也就是我们挑选物品没有考虑顺序，而本题是要考虑顺序的，因此本题不能用"完全背包"的方法来解决

1.状态表示

本题的状态表示方式是之前的博客没有提到的:

根据分析问题的过程中，发现重复子问题，抽象出一个状态表示

[a, b, c, d, e], 在整个区间中选择凑成总和为target, 如果第一个数选了a, 那只需要在整个区间凑成总和为target-a即可, 于是我们发现了重复子问题

dp[i]表示: 凑成总和为 i, 一共有多少种排列数

2.状态转移方程

3.初始化

dp[0] = 1，因为数组中元素>=1，因此要凑出总和为0, 什么都不选，也就是空集

4.填表顺序

从左往右

5.返回值

dp[target]

3.算法代码

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<double> dp(target+1);dp[0] = 1;for(int i = 1; i <= target; i++)for(auto x : nums)if(i >= x) dp[i] += dp[i-x];return dp[target];}
};

卡特兰数

不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/unique-binary-search-trees/description/1.题目解析

给定整数n, 求由n个节点(值是1到n)组成的二叉搜索树有多少种

2.算法分析

1.状态表示 --- 根据分析问题的过程中，发现重复子问题，抽象出一个状态表示

随便选一个数，作为根，此时就只需要分析左子树和右子树有多少种二叉搜索树, 然后乘起来

dp[i]表示: 节点个数为i时，一共有多少种二叉搜索树

2.状态转移方程

节点为[1, 2, ... i], 随便选一个数j作为根，则左子树的节点个数为j-1, 右子树的节点个数为i-j,

dp[i] += dp[j-1] * dp[i-j]

(1<= j <= i)

3.初始化

dp[0] = 1，空树也是一颗二叉搜索树

4.填表顺序

从左往右

5.返回值

dp[n]

3.算法代码

class Solution {
public:int numTrees(int n) {vector<int> dp(n+1);dp[0] = 1;for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)dp[i] += dp[j-1] * dp[i-j];return dp[n];}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/329740.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Sui生态DeFi项目Cetus和Aftermath宣布启动孵化器

Sui生态DeFi项目Cetus和Aftermath宣布启动孵化器

Sui DeFi中的去中心化交易所Cetus和Aftermath Finance联合Sui基金会宣布启动新的孵化器&#xff0c;为初创项目提供更多可行性途径。这两个DeFi项目在Sui上有着较长的历史&#xff0c;自去年一同与主网推出以来&#xff0c;目前在TVL方面位居前五。这两个项目的持久性和成功使它…
阅读更多...
《Effective Objective-C 2.0》读书笔记——接口与API设计

《Effective Objective-C 2.0》读书笔记——接口与API设计

目录 第三章&#xff1a;接口与API设计第15条&#xff1a;用前缀避免命名空间冲突第16条&#xff1a;提供“全能初始化方法”第17条&#xff1a;实现description方法第18条&#xff1a;尽量使用不可变对象第19条&#xff1a;使用清晰而协调的命名方式第20条&#xff1a;为私有方…
阅读更多...
计算机网络协议

计算机网络协议

网络协议 基于TCP的应用层协议 POP3&#xff08;Post Office Protocol 3&#xff09;&#xff1a; 用于支持客户端远程管理服务器上的电子邮件。它支持**“离线”邮件处理**&#xff0c;即邮件发送到服务器上后&#xff0c;一旦邮件被POP3客户端下载到本地计算机&#xff0c;…
阅读更多...
Redis --学习笔记

Redis --学习笔记

Redis简介 一个基于内存的key-value结构数据库。Redis 是互联网技术领域使用最为广泛的存储中间件 特点&#xff1a; 基于内存存储&#xff0c;读写性能高 适合存储热点数据&#xff08;热点商品、资讯、新闻&#xff09; 企业应用广泛 Redis默认端口号为6379 Redis是用…
阅读更多...
Unity射击游戏开发教程：（24）创造不同的敌人

Unity射击游戏开发教程：（24）创造不同的敌人

在这篇文章中，我们将讨论添加一个可以承受多次攻击的新敌人和一些动画来使事情变得栩栩如生。敌人没有任何移动或射击行为。这将有助于增强未来敌人的力量。 我们将声明一个 int 来存储敌人可以承受的攻击数量，并将其设置为 3。
阅读更多...
力扣刷题---1748.唯一元素的和【简单】

力扣刷题---1748.唯一元素的和【简单】

题目描述 给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。 请你返回 nums 中唯一元素的 和 。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3,2] 输出&#xff1a;4 解释&#xff1a;唯一元素为 [1,3] &#xff0c;和为 4 。 示例 2&#xff1a;…
阅读更多...
NLP(16)--生成式任务

NLP(16)--生成式任务

前言 仅记录学习过程&#xff0c;有问题欢迎讨论 输入输出均为不定长序列&#xff08;seq2seq&#xff09;自回归语言模型&#xff1a; x 为 str[start : end ]; y为 [start1 : end 1] 同时训练多个字&#xff0c;逐字计算交叉熵 encode-decode结构&#xff1a; Encoder将输…
阅读更多...
微服务远程调用 RestTemplate

微服务远程调用 RestTemplate

Spring给我们提供了一个RestTemplate的API&#xff0c;可以方便的实现Http请求的发送。 同步客户端执行HTTP请求&#xff0c;在底层HTTP客户端库(如JDK HttpURLConnection、Apache HttpComponents等)上公开一个简单的模板方法API。RestTemplate通过HTTP方法为常见场景提供了模…
阅读更多...
从ES5迈向ES6：探索 JavaScript 新增声明命令与解构赋值的魅力

从ES5迈向ES6：探索 JavaScript 新增声明命令与解构赋值的魅力

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;JavaScript 精粹 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; ES5、ES6介绍 文章目录 &#x1f4af;声明命令 let、const&#x1f35f;1 let声明符&a…
阅读更多...
【LeetCode】每日一题 2024_5_24 找出最具竞争力的子序列（栈，模拟，贪心）

【LeetCode】每日一题 2024_5_24 找出最具竞争力的子序列（栈，模拟，贪心）

文章目录 LeetCode&#xff1f;启动&#xff01;&#xff01;&#xff01;题目&#xff1a;找出最具竞争力的子序列题目描述代码与解题思路 每天进步一点点 LeetCode&#xff1f;启动&#xff01;&#xff01;&#xff01; 题目&#xff1a;找出最具竞争力的子序列 题目链接&a…
阅读更多...
【Unity2D：C#Script】实现角色射击功能

【Unity2D：C#Script】实现角色射击功能

一、创建子弹预制体 1. 创建子弹预制体 2. 调整图片大小、层级 二、为子弹添加碰撞体积 1. 添加Box Collider 2D、Rigidbody 2D组件 2. 锁定z轴 三、编辑敌人脚本 注&#xff1a;在以下代码中&#xff0c;只显示本章节新增的代码&#xff0c;省略原有的代码 1. 为敌人添加生…
阅读更多...
一阶数字高通滤波器

一阶数字高通滤波器

本文的主要内容包含一阶高通滤波器公式的推导和数字算法的实现以及编程和仿真 1 计算公式推导 1.1.2 算法实现及仿真 利用python实现的代码如下&#xff1a; import numpy as np # from scipy.signal import butter, lfilter, freqz import matplotlib.pyplot as plt #2pifW…
阅读更多...
免费分享一套微信小程序旅游推荐(智慧旅游)系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】，帅呆了~~

免费分享一套微信小程序旅游推荐(智慧旅游)系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】，帅呆了~~

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序旅游推荐(智慧旅游)系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序旅游推荐(智慧旅游)系统(SpringBoot后端Vue管理端) Java毕业设计…
阅读更多...
视频监控管理平台LntonCVS监控视频汇聚融合云平台主要功能应用场景介绍

视频监控管理平台LntonCVS监控视频汇聚融合云平台主要功能应用场景介绍

随着网络技术的不断发展和万物互联时代的到来&#xff0c;视频融合在一些系统集成项目及综合管理应用中变得日益重要。本文以LntonCVS视频融合云平台为案例&#xff0c;探讨视频融合的对象及其应用场景。 1. 视频监控设备 视频监控摄像设备是各种视频应用项目的基础部分。在视…
阅读更多...
亚马逊卖家账号注册复杂吗？需要什么辅助工具吗？

亚马逊卖家账号注册复杂吗？需要什么辅助工具吗？

在当今数字化的商业世界中&#xff0c;亚马逊作为全球最大的电商平台之一&#xff0c;吸引着无数的卖家和买家。对于想要进入亚马逊销售市场的卖家来说&#xff0c;首先要完成的一项重要任务就是注册亚马逊卖家账号。本文将详细介绍亚马逊注册的步骤、所需时间&#xff0c;以及…
阅读更多...
入门四认识HTML

入门四认识HTML

一、HTML介绍 1、Web前端三大核心技术 HTML&#xff1a;负责网页的架构 CSS&#xff1a;负责网页的样式、美化 JS&#xff1a;负责网页的行动 2、什么是HTML HTML是用来描述网页的一种语言。 3、Html标签 单标签<html> 双标签<h>内容</h> 4、标…
阅读更多...
【译】组复制和 Percona XtraDB 集群： 常见操作概述

【译】组复制和 Percona XtraDB 集群： 常见操作概述

原文地址&#xff1a;Group Replication and Percona XtraDB Cluster: Overview of Common Operations 在这篇博文中&#xff0c;我将概述使用 MySQL Group Replication 8.0.19&#xff08;又称 GR&#xff09;和 Percona XtraDB Cluster 8 (PXC)&#xff08;基于 Galera&…
阅读更多...
服务器数据恢复—EVA存储多块硬盘离线导致部分LUN丢失的数据恢复案例

服务器数据恢复—EVA存储多块硬盘离线导致部分LUN丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 1台某品牌EVA4400控制器3台EVA4400扩展柜28块FC硬盘。 服务器故障&#xff1a; 由于两块磁盘掉线导致存储中某些LUN不可用&#xff0c;某些LUN丢失&#xff0c;导致存储崩溃。 服务器数据恢复过程&#xff1a; 1、由于EVA4400存储故障是某些磁…
阅读更多...
Java 对外API接口开发 java开发api接口如何编写

Java 对外API接口开发 java开发api接口如何编写

Java API API&#xff08;Application Programming Interface&#xff09;是指应用程序编程接口&#xff0c;的JavaAPI是指JDK提供的各种功能的Java类 String类 String类的初始化&#xff1a; &#xff08;1&#xff09;使用字符串常量直接初始化 初始化&#xff1a;String s…
阅读更多...
闲话 .NET（4）：为什么要跨平台？

闲话 .NET（4）：为什么要跨平台？

前言 .NET Core 有一个关键词就是跨平台&#xff0c;为什么要跨平台呢&#xff1f;Windows 操作系统不香吗&#xff1f;今天我们来聊聊这个 原因一&#xff1a;安全考虑 Windows OS 是闭源的&#xff0c;而 Linux 是开源的&#xff0c;因此有些公司的技术负责人就认为 Linux…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023