给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100
题目理解失败：还以为是数组中每个元素的01个数与m和n的比较。
func findMaxForm(strs []string, m int, n int) int {
result := 0
for i:=0;i<len(strs);i++{
m0 := strings.Count(strs[i],"0")
n1 := strings.Count(strs[i],"1")
if m0+n1<m+n&&m0<=m&&n1<=n{
result++
}
}
return result
}
正确理解：数组中由各个元素组成的01个数不大于m和n的组合。
例子：
strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
最大的集合为：{"10","0001","1","0"}。这里0的个数为5，1的个数为3。并且也是最大的组合。
贪心算法：思路错误
将数组中的元素，按照元素的长度进行重新排序。然后从长度最小进行匹配，直到遍历结束或者m和n都等于0。但是当元素的长度都相等的时候，思路错误。
func findMaxForm(strs []string, m int, n int) int {
sort.Strings(strs)
head0 := []string{}
head1 := []string{}
for i:=0;i<len(strs);i++{
if string(strs[i][0])=="0" {
head0 = append(head0,strs[i])
}else if string(strs[i][0])=="1" {
head1 = append(head1,strs[i])
}
}
// 归并
x,y := 0,0
tmp := []string{}
for x<len(head0)&&y<len(head1) {
if len(head0[x]) <= len(head1[y]) {
tmp = append(tmp,head0[x])
x++
}else if len(head0[x]) > len(head1[y]) {
tmp = append(tmp,head1[y])
y++
}
}
if x<len(head0) {
tmp = append(tmp,head0[x:]...)
}
if y<len(head1) {
tmp = append(tmp,head1[y:]...)
}
log.Println(tmp)
// 从这里开始执行贪心算法，直接从长度最小的开始算起，直到满足条件
result := 0
for i:=0;i<len(tmp);i++{
m0 := strings.Count(tmp[i],"0")
n1 := strings.Count(tmp[i],"1")
if m0<=m&&n1<=n {
result++
m=m-m0
n=n-n1
}
}
return result
}
正确做法
这道题跟经典的背包问题相似。背包问题使用的是动态规划的解法，并且使用的是二维数组，两个维度分别表示为物品和容量。这道题的容量为0和1的个数，有两个，因此需要用三维数组表示。其中三维数组的维度分别代表为：字符串、0的容量和1的容量。并且三维数组的每个元素的代表，即dp[i]/[j]/[k]代表为：有i个字符串、j个0和k个1的情况下最多可以得到的字符串数量。假设数组长度为l，则最终答案为dp[l]/[j]/[k]。
当没有字符串的时候，可以得到dp[0]/[j]/[k]的值都为0。当1<=i<=l的时候，对于strs中的第i个字符串（计数从1开始），首先遍历该字符串0的个数和1的个数，分别记为：zeros和ones，然后0<=j<=m和0<=k<=n，计算dp[i]/[j]/[k]的值。
当0和1的容量分别是i和j的时候，考虑以下两种情况：
- 如果j<zeros和k<ones时，则不能选择这个字符串，此时有dp[i]/[j]/[k]=dp[i−1]/[j]/[k]。
- 如果j>=zeros和k>ones时，则如果不选择这个字符串，此时有dp[i]/[j]/[k]=dp[i−1]/[j]/[k]。如果选择这个字符串，有dp[i]/[j]/[k]=dp[i-1]/[j-zeros]/[k-ones]+1。因此对于这两种情况的选择，根据题意选择最大的为当前值。
实现代码
// m代表0的个数，n代表1的个数
func findMaxForm(strs []string, m int, n int) int {
// 背包问题的转化而已，只不过容量有两个而已
length := len(strs)
dp := make([][][]int,length+1) // 为什么不是length呢？因为要取到dp[length]的下标
for i:=range dp{
dp[i] = make([][]int,m+1) // 同上
for j:=range dp[i] {
dp[i][j] = make([]int,n+1) // 同上
}
}
for i,s := range strs{ // i的表示字符个数
zeros := strings.Count(s,"0")
ones := len(s)-zeros
for j:=0;j<=m;j++{ // 表示有多少个0
for k:=0;k<=n;k++{ // 表示有多少个1
dp[i+1][j][k] = dp[i][j][k]
if j>=zeros&&k>=ones {
dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j-zeros][k-ones]+1) // 表示取第i个字符串的时候，总共得到的字符串个数
}
}
}
}
return dp[length][m][n]
}
func max(x,y int)int{
if x>y {
return x
}
return y
}