package main

import (
	. "github.com/9d77v/leetcode/pkg/algorithm/math"
)

/*
题目：一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

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

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

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ones-and-zeroes
*/

/*
方法一：动态规划
时间复杂度： О(n^2)
空间复杂度：О(n^2)
运行时间：28 ms	内存消耗：3.7 MB
*/
func findMaxForm(strs []string, m int, n int) int {
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for _, s := range strs {
		cnt := [2]int{}
		for i := range s {
			cnt[s[i]-'0']++
		}
		for i := m; i >= cnt[0]; i-- {
			for j := n; j >= cnt[1]; j-- {
				f[i][j] = Max(f[i][j], f[i-cnt[0]][j-cnt[1]]+1)
			}
		}
	}
	return f[m][n]
}
