目录

• • 题目思路
  • 动态规划
  • 动态规划(压缩)

题目来源
474. 一和零

题目思路

为了方便理解, 先把两个变量删掉一个, 那么题目变为: 返回最大子集的长度,该子集中最多有m个0
此时的解题思路就是正常的二维dp:

1.创建一个dp[len+1][m+1], 其中len = strs.length.
2.dp[i][j] 代表: 在[0-i]个字符串中, 0有i个时最多有几个子串.
3.那么递推公式:

if( i-zeros>=0) : dp[i][j] = Math.max(dp[i][j], dp[i-1][i-zeros] + 1); else : dp[i][j] = dp[i-1][j];
其中zeros=该字符串中0的数量.
解释一下这里为什么是dp[i-1][j-zeros] + 1, 因为如果要把当前第i个字符串算入子串的话, 需要zeros的容量, 所以前i-1的子串最多只能占i-zeros的容量.

理解了上面所说的一个变量的情况, 那么两个变量的情况就简单了, 就是在dp[len+1][m+1]后再加一个维度变成dp[len+1][m+1][n+1].

此时dp[i][j][k] 代表: 在[0-i]个字符串中, 0有j个, 1有k个时最多有几个子串.
递推公式变成:

if( j-zeros >= 0 && k-ones>=0) : dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1); else: dp[i][j][k] = dp[i-1][j][k];
其中zeros=该字符串中0的数量. ones代表该字符串中1的数量.
解释一下这里为什么是dp[i-1][j-zeros][k-ones] + 1, 因为如果要把当前第l个字符串算入子串的话, 需要zeros和ones的容量, 所以前i-1的子串最多只能占[j-zeros] && [k-ones]的容量.

动态规划

class Solution {public int findMaxForm(String[] strs, int m, int n) {if(strs == null){return 0;}int[][][] dp = new int[strs.length+1][m+1][n+1];for(int i=1;i<=strs.length;i++){int zero = 0;int one = 0;String str = strs[i-1];for (int x = 0; x < str.length(); x++){if (str.charAt(x) == '0')zero++;elseone++;}for(int j = 0;j<=m;j++){for(int k=0;k<=n;k++){if(j>=zero && k>=one){dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zero][k-one]+1);}else{dp[i][j][k] = dp[i-1][j][k];}}}}return dp[strs.length][m][n];}
}

动态规划(压缩)

• 1.确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

• 2.确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。
这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

• 3.dp数组如何初始化

因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

• 4.确定遍历顺序

外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n。

        for(String str :strs){int zero = 0;int one = 0;for (char ch : str.toCharArray()) {if (ch == '0') {zero++;} else {one++;}}//倒序遍历for (int i = m; i >= zero; i--) {for (int j = n; j >= one; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);}}}

• 5.举例推导dp数组

以输入：[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3为例
最后dp数组的状态如下所示：

代码如下

class Solution {public int findMaxForm(String[] strs, int m, int n) {if(strs == null){return 0;}int[][] dp = new int[m+1][n+1];for(String str :strs){int zero = 0;int one = 0;for (char ch : str.toCharArray()) {if (ch == '0') {zero++;} else {one++;}}//倒序遍历for (int i = m; i >= zero; i--) {for (int j = n; j >= one; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);}}}return dp[m][n];}
}