474. 一和零
474. 一和零
分析
这道题很明显也是 KM-46. 携带研究材料，经典的 01 背包问题是将物品放到背包中，物品有大小和价值两重属性，背包的容量大小有限，求能放下的物品的最大价值，这里，背包的限制只有大小，也就是说限制只有一个（一维的），但是这个题中，我们要选的物品（01 字符串）的只有一重属性，就是字符串本身，而背包的限制有两个，总的 0 的个数和总的 1 的个数，也就是说，限制是二维的，然后我们要求的值，是物品的个数。由于背包的限制是二维的，因此，没有别的选择，我们只能用一个三维的 dp 数组（一维遍历物品，一维遍历 0 的个数，一维遍历 1 的个数），
我们先以三维 dp 为例，然后再讲解二维
首先遍历数组的所有元素，将 0 的个数和 1 的个数记录到 count 中。
定义 dp 数组：dp[i][j][k] 的含义是，从索引 0 到索引 i 这些元素中，选择元素组成子集，子集中的所有元素满足 0 的个数最多为 j，1 的个数最多为 k，此时子集的最大子集的长度就是 dp[i][j][k]。
跟 KM-46. 携带研究材料 一样，本题只是背包变成了二维的，实际上的逻辑还是一样的，就是看这个子集包不包含物品 i：
- 不包含物品 i，
dp[i][j][k]=dp[i-1][j][k]； - 包含物品 i，
dp[i][j][k]=dp[i-1][j-count[i][0]][k-count[i][1]] + 1；
最长的子集就是这两个数字中的最大值，因此状态转移方程就是 dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-count[i][0]][k-count[i][1]]+1)
然后就是初始化，
- 当 i 为 0 的时候，即只有物品 0 的时候，需要初始化
dp[0][j][k]，只有j=count[i][0]而且k=count[i][1]的时候，dp[i][j][k] = 1，其他 j 或者 k 值都为 0。 - 当 j 为 0 的时候，需要初始化
dp[i][0][k]，这个需要遍历所有的元素，碰到一个只包含 1 的元素，就更新dp[i][0][k]的值 - 当 k 为 0 的时候，需要初始化
dp[i][j][0]，这个需要遍历所有的元素，碰到一个只包含 0 的元素，就更新dp[i][j][0]的值
这个初始化有点复杂。
然后遍历顺序是，最外层遍历物品 i，里面两层遍历 0 的个数 j 和 1 的个数 k。总共三层遍历
当然，如果足够熟练，我们可以直接使用二维版本的（一维遍历 0 的个数，一维遍历 1 的个数）。
首先定义 dp 数组：dp[j][k] 的含义是，strs 中包含最多 j 个 0 和 k 个 1 的子集的最大长度。
然后状态转移方程就是 dp[j][k] = Math.max(dp[j][k],dp[j-count[i][0]][k-count[i][1]]+1)
初始化的时候，参考 KM-46. 携带研究材料#优化，我们是从 i=0 的时候开始遍历，所以我们实际上是在没有选择任何物品的场景下初始化 dp 数组，而没有选择任何元素的情况下，dp[j][k] 始终为 0。
然后遍历顺序是，最外层遍历物品，第二层先倒序遍历 0 的个数 j ，第三层倒叙遍历 1 的个数 k。
一个小优化
将求 count 的 for 循环放到求 dp 数组中，可以节约一点性能。
解题
原始版本：
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] count = new int[strs.length][2];
for(int i=0;i<strs.length;i++){
String str = strs[i];
int num0= 0;
int num1= 0;
for(char c:str.toCharArray()){
if('0'==c){
num0++;
}
if('1'==c){
num1++;
}
}
int[] num ={num0,num1};
count[i] = num;
}
// 开始构造dp数组
int[][] dp = new int[m+1][n+1];
for(int i=0;i<strs.length;i++){
for(int j=m;j>=count[i][0];j--){
for(int k=n;k>=count[i][1];k--){
dp[j][k] = Math.max(dp[j][k],dp[j-count[i][0]][k-count[i][1]]+1);
}
}
}
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];
}
相关题
另一个求物品个数的题