本篇博客给大家带来的是二维01背包问题之动态规划解法技巧.
🐎文章专栏: 动态规划
🚀若有问题 评论区见
❤ 欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .
要开心
要快乐
顺便进步
1. 一和零
题目链接: 474. 一和零
题目内容:
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。
第一步 分析
在前面学习01背包问题和完全背包问题的时候, 我们遇到的限制条件只有一个, 这道题中出现了两个:
最多 有 m 个 0 和 n 个 1
只有一个限定条件的01背包问题的状态表示是这样定义的: dp[i][j]表示 从前 i 个物品中选, 总体积不超过 j ,所有选法的最大价值.
类比过来本题的状态表示可以这么定义:
dp[i][j][k]表示从前 i 个字符串中挑选, 字符0个数不超过 j , 字符1 的个数不超过 k,所有选法中的最大长度.
第二步 动态规划
1. 状态表示
dp[i][j][k]表示从前 i 个字符串中挑选, 字符0个数不超过 j , 字符1 的个数不超过 k,所有选法中的最大长度.
2. 状态转移方程
以某 i 位置是否选择来划分情况:
如果选了strs[i]的话, j需要减去strs[i]含有的0个数,k需要减去strs[j]含有的1个数. 这里假设strs[i]有a个0,b个1;
不选strs[i]: dp[i][j][k] = dp[i-1][j][k];①
选了strs[i]: dp[i][j][k] = dp[i-1][j-a][k-b];②
结合①②又 题目所求的是最大子集长度,所以:
dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-a][k-b]+1);
②式应用的前提是: j >= a && k >= b
3. 初始化
多创建了一行一列一竖,处理两个细节:
1. dp表与原数组下标之间的对应关系:
因为状态转移方程中并没有涉及到原数组strs的式子,所以可以不用管这一步.
2. 初始化虚拟节点:
因为有j >= a && k >= b的限制(在一维的题中有解释过,具体可以看我之前的文章),所以只需初始化i = 0的节点即可, i=0 的时候没有字符串课选,最大长度为0,所以dp[0][j][k] = 0;
4. 填表顺序
看状态转移方程,
要想填dp[i][j][k] 就得直到dp[i-1][j][k] 和 dp[i-1][j-a][k-b], 所以需要保证 i 按小到大的顺序去填写.
5. 返回值
根据状态表示并结合题目要求,返回dp[strs.length()][m][n]即可.
6. 代码优化
跟01背包问题的优化方式一毛一样,
删掉第一维[i],然后 两层for循环的填表顺序改为从大到小.
详细看01背包问题, 文章链接: 01背包问题
第三步 代码实现
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
//优化前:
// int len = strs.length;
// int[][][] dp = new int[len+1][m+1][n+1];
// for(int i = 1;i <= len;++i) {
// //统计各个字符串的个数
// int a = 0;//记录0的个数
// int b = 0;//记录1的个数
// for(char ch : strs[i-1].toCharArray()) {
// 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] = Math.max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
// }
// }
// }
// }
// return dp[len][m][n];
//优化后:
int len = strs.length;
int[][] dp = new int[m+1][n+1];
for(int i = 1;i <= len;++i) {
//统计各个字符串的个数
int a = 0;//记录0的个数
int b = 0;//记录1的个数
for(char ch : strs[i-1].toCharArray()) {
if(ch == '0') {
a++;
}else {
b++;
}
}
for(int j = m;j >= a;--j) {
for(int k = n;k >= b;--k) {
dp[j][k] = Math.max(dp[j][k],dp[j-a][k-b]+1);
}
}
}
return dp[m][n];
}
}
2. 盈利计划
题目链接: 879. 盈利计划
题目内容:
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
示例 1：
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。
示例 2：
输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
第一步 动态规划
1. 状态表示
dp[i][j][k]表示在前 i 个工作中选,参与成员总数不超过 j,产生的利润至少为k,总共有多少种选法.
2. 状态转移方程
根据 i 位置的 选择与否来划分情况:
profit[i]不选, dp[i][j][k] = dp[i-1][ j][k];①
profit[i]选, dp[i][j][k] = dp[i-1][ j-group[i]][k-profit[i]].Ⅱ
考虑到profit[i] 有可能大于 k,而数组的下标不能为负数. 所以Ⅱ式不能这么写.那要怎么办呢?
如果profit[i] > k, 但是profit[i]利润就满足了条件 那么前i-1个位置的利润可以为0.
所以, dp[i][j][k] = dp[i-1][ j-group[i]][Math.max(0,(k-profit[i]))];②
根据①②并结合题目要求
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i]][Math.max(0,(k-profit[i]))];
使用②式的前提是: j >= group[i] && k <= profit[i];
3. 初始化
多创建了一行一列一竖,处理两个细节:
1. dp表与原数组下标之间的对应关系:
i – i-1;
2. 初始化虚拟节点.
j 和 k都是有限制的,j = 0和k = 0在填表中填即可, 主要初始化 i=0时的情况.
当i=0 && k =0时,
无论 j 是多少dp[0][j][0] = 1;
即当没有工作的时候,利润至少为0,人数不超过 j.有几种选法, 只有一种,就是不选.
4. 填表顺序
与上一道题一样, i从小到大填写.
5. 返回值
根据状态表示并结合题目要求: return dp[profit.length][n][minprofit];
6. 优化
1. 删除第一维[i]
2. 两层for循环的填表顺序改为从大到小
第二步 代码实现
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
//优化前:
// int m = profit.length;
// int[][][] dp = new int[m+1][n+1][minProfit+1];
// //2. 初始化
// for(int i = 0;i <= n;i++) {
// dp[0][i][0] = 1;
// }
// for(int i = 1;i <= m;++i) {
// for(int j = 0;j <= n;++j) {
// for(int k = 0;k <= minProfit;++k) {
// dp[i][j][k] += dp[i-1][j][k];
// if(j >= group[i-1]) {
// dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
// dp[i][j][k] %= 1e9+7;
// }
// }
// }
// }
// return dp[m][n][minProfit];
//优化后:
int m = profit.length;
int[][] dp = new int[n+1][minProfit+1];
//2. 初始化
for(int i = 0;i <= n;i++) {
dp[i][0] = 1;
}
for(int i = 1;i <= m;++i) {
for(int j = n;j >= group[i-1];--j) { // 从右往左遍历
for(int k = minProfit;k >= 0;--k) {
dp[j][k] += dp[j-group[i-1]][Math.max(0,k-profit[i-1])];
dp[j][k] %= 1e9+7;
}
}
}
return dp[n][minProfit];
}
}
本篇博客到这里就结束啦, 感谢观看 ❤❤❤
🐎期待与你的下一次相遇😊😊😊