怎样做免费商城网站,竞价代运营公司哪家好,网站统计付费,做网站软件war题目链接#xff1a;474. 一和零 - 力扣#xff08;LeetCode#xff09;
前情提要#xff1a;
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
最近刚学完01背包#xff0c;所以现在的题解都是以01背包问题为基础再来写的。
如果大家不懂01背包的话#…题目链接474. 一和零 - 力扣LeetCode
前情提要
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
最近刚学完01背包所以现在的题解都是以01背包问题为基础再来写的。
如果大家不懂01背包的话建议可以去学一学01背包问题可以说是背包问题的基础。 如果大家感兴趣我后期可以出一篇专门讲解01背包问题。 dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚那么这道题就能解出来了。
题目思路:
本题要求的是m个0n个1时子集中的最大长度。
其实这m个0n个1就是一种容器我们要将该容器装满求得子集的最大长度即可。
那么可以将这种容器抽象为背包只不过这个背包是二维的最大容量为m个0n个1。
那么问题可以转化为将这个背包装满求物品的数量。
接下来我们用动规五部曲来系统分析一下。
1.确定dp数组和i下标的含义。
我们这个背包是二维的所以我们的dp数组也得是二维的。
dp[i] [j]指有i个0m个1时最大能装的物品数量。
2.确定递推公式。
首先我们来看看纯01背包问题的递推公式。
dp[j] Math.max(dp[j],dp[j - weight[i]] value[i])
那么本题的递推公式其实和01背包递推公式相似。
每个物品只有选和不选俩种状态。
不选的话就是dp[i] [j]因为没有选该物品所以背包容量不变。
选的话就是dp[i - x] [j - y] 1;其实x表示的是当前物品0的数量y表示当前物品1的数量。
因为选的话就得求出加入当前物品之前的背包容量能装入的最大物品数量再加上该物品。也就是 1
所以我们的递推公式就是 dp[i] [j] Math.max(dp[i] [j],dp [i - x] [j - y] 1);
3.dp初始化。
dp[0] [0]指的就是当背包中有0个0和0个1时能装入的物品数量所以dp[0] [0] 0
其他的非0下标可以通过dp数组推出来所以其他的我们就不初始化没有意义。
4.确定dp的遍历顺序。
该题与01背包的遍历顺序相同物品从前往后遍历背包容量从后往前遍历上为了保证每个物品只放入了一次。
5.如果没有ac打印dp数组 利于debug。
如果没有出现差错我们就可以不用打印因为我是写题解所以我就不添加核心代码以外的代码不然代码显的有些冗余。
举个例子。 最终代码
class Solution {public int findMaxForm(String[] strs, int m, int n) {// 本题核心思路就是把这个背包装满最多能装多少物品。//同时本题背包具有俩个维度。//递推公式 dp[i][j]是指在i个0j个1下能装满的物品数量。//那么每个物品也只有选和不选该物品不选就是dp[i][j]//选的话就是dp[i - x][j - y] 1,选择该物品的话要将装入前能装的最多物品加1也就是加上这个物品//本题是把每个子集当做一个物品//确定dp数组int dp[][] new int[m 1][n 1];//初始化dp数组dp[0][0] 0;//遍历物品for (String s : strs) {int x 0, y 0;//统计每个物品的01数量for (int v 0;v s.length();v ) {if (s.charAt(v) 0) {x;} else {y;}}//遍历背包//由于背包是俩个维度所以俩个要从后往前遍历 确保物品只放入了一次for (int i m; i x; i--) {for (int j n; j y; j--) {//递推公式dp[i][j] Math.max(dp[i][j], dp[i - x][j - y] 1);}}}return dp[m][n];}
}这一篇博客就到这了如果你有什么疑问和想法可以打在评论区或者私信我。
我很乐意为你解答。那么我们下篇再见
