LeetCode（12）一和零（中等）

题目描述：

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ones-and-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (String s: strs) {
int[] count = countzeroesones(s);
for (int zeroes = m; zeroes >= count[0]; zeroes--)
for (int ones = n; ones >= count[1]; ones--)
dp[zeroes][ones] = Math.max(1 + dp[zeroes - count[0]][ones - count[1]], dp[zeroes][ones]);
}
return dp[m][n];
}
public int[] countzeroesones(String s) {
int[] c = new int[2];
for (int i = 0; i < s.length(); i++) {
c[s.charAt(i)-‘0‘]++;
}
return c;
}
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/ones-and-zeroes/solution/yi-he-ling-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

值得注意的是；

这个问题类似于背包问题，把每个元素的0和1数量统计然后 尝试放入最大容量为[m][n]的背包(同时容量减小)

如果放的下就放[m][n-1]的背包 直到放不下 放[m-1][n]的背包 以此类推 把所有元素和各种背包都遍历完

得出dp[m][n]的值。

LeetCode（12）一和零（中等）

原文：https://www.cnblogs.com/ash98/p/14730281.html