江西网站设计方案网站优化关键词价格

题目链接：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个0，n个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];}
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！