474. 一和零
474. 一和零
分析
这道题很明显也是 背包问题-01背包，经典的 01 背包问题是将物品放到背包中，物品有大小和价值两重属性，背包的容量大小有限，求能放下的物品的最大价值，这里，背包的限制只有大小，也就是说限制只有一个（一维的），但是这个题中，我们要选的物品（01 字符串）的只有一重属性，就是字符串本身，而背包的限制有两个，总的 0 的个数和总的 1 的个数，也就是说，限制是二维的，然后我们要求的值，是物品的个数。由于背包的限制是二维的，因此，没有别的选择，我们只能用一个三维的 dp 数组（一维遍历物品，一维遍历 0 的个数，一维遍历 1 的个数），当然，如果足够熟练，我们可以直接使用二维版本的（一维遍历 0 的个数，一维遍历 1 的个数）。
以下我们就以二维版本的来分析：
首先定义 dp 数组：dp[j][k] 的含义是，strs 中包含最多 j 个 0 和 k 个 0 的子集的长度。
我们首先将物品 i 中包含的 0 的个数放到数组 mvalue 中，将其中包含的 1 的个数放到 nvalue 中。
然后我们确定状态转移方程，对于物品 i 来说，只有两种选择，就是把物品 i 放到背包里，和不把物品 i 放到背包里，如果不把物品 i 放到背包里，那么直接沿用从物品 0 到物品 i-1 的结果即可，即 dp[i-1][j][k]，在二维版本里，就是 dp[j][k]，如果放了物品 i，那么子集的长度就变成了 1（当前元素）加上 dp[i-1][j-mvalue[i]][k-nvalue[i]]，在二维版本里，就是 1+dp[j-mvalue[i]][k-nvalue[i]]。最终，我们确定的状态转移方程是：dp[j][k] = Math.max(dp[j][k],1+dp[j-mvalue[i]][k-nvalue[i]])。
初始化，dp[0][0]=0，其实也可以不这样初始化。
然后遍历顺序是，最外层遍历物品，里面两层遍历 0 的个数 j 和 1 的个数 k。总共三层遍历
一个小优化
我原本想的优化方向是如何不使用两个 for 循环来计算 dp（那样的话 dp 就不能是二维数组当前组合），然后我发现这道题只能这样做。
然后将求 mvalue 和 nvalue 的两个嵌套 for 循环放到求 dp 数组中，可以节约一点性能。
解题
原始版本：
public int findMaxForm(String[] strs, int m, int n) {
// 将每一个元素的m和n求出来
int[][] mvalue = new int[strs.length][1];
int[][] nvalue = new int[strs.length][1];
for (int i = 0; i < strs.length; i++) {
char[] chars = strs[i].toCharArray();
for (char c : chars) {
if ('0' == c) {
mvalue[i][0]++;
} else if ('1' == c) {
nvalue[i][0]++;
}
}
}
// 从三维dp，降到2维dp，因为背包，有两个条件
// 最终我们要求的是 dp[m][n]
int[][] dp = new int[m + 1][n + 1];
// 核心推导过程依然是放与不妨物品i
// 状态转移
// dp[j][k] = Math.max(dp[j][k],1+dp[j-mvalue[i]][k-nvalue[i]])
// 初始化
dp[0][0] = 0;
for (int i = 0; i < strs.length; i++) {
for (int j = m; j >= mvalue[i][0]; j--) {
for (int k = n; k >= nvalue[i][0]; k--) {
dp[j][k] = Math.max(dp[j][k], 1 + dp[j - mvalue[i][0]][k - nvalue[i][0]]);
}
}
}
return dp[m][n];
}
优化一点儿的版本：
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
// 初始化
dp[0][0] = 0;
for (int i = 0; i < strs.length; i++) {
int zeroCount = 0;
int oneCount = 0;
char[] chars = strs[i].toCharArray();
for (char c : chars) {
if ('0' == c) {
zeroCount++;
} else if ('1' == c) {
oneCount++;
}
}
for (int j = m; j >= zeroCount; j--) {
for (int k = n; k >= oneCount; k--) {
dp[j][k] = Math.max(dp[j][k], 1 + dp[j - zeroCount][k - oneCount]);
}
}
}
return dp[m][n];
}