474. 一和零

给你一个二进制字符串数组 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 。

  1. //三维dp，01🎒，时间 lmn ;空间 lmn
  2. func findMaxForm(strs []string, m int, n int) int {
  3.     l := len(strs)
  4.     dp := make([][][]int, l +1)
  6.     for k := range dp {
  7.         dp[k] = make([][]int, m +1)
  8.         for k1 := range dp[k] {
  9.             dp[k][k1] = make([]int, n +1)
  10.         }
  11.     }
  13.     for i := 1; i <= l; i++ {
  14.         count := countZeroAndOne(strs[i-1])      //新的函数，用来判断数组的数字个数
  15.         for j := 0; j <= m; j++ {
  16.             for k := 0; k <= n; k++ {
  17.                 if count[0] > j || count[1] > k {
  18.                     dp[i][j][k] = dp[i-1][j][k]         //不装包，超容量了
  19.                 } else {
  20.                     dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j- count[0]][k- count[1]] +1)
  21.                 }
  22.             }
  23.         }
  24.     }
  25.     return dp[l][m][n]
  26. }
  28. func countZeroAndOne(s string) []int {
  29.     c := make([]int, 2)
  30.     for i := 0; i < len(s); i++ {
  31.         c[s[i]-'0']++
  32.     }
  33.     return c
  34. }
  36. func max(a, b int) int {
  37.     if a > b {
  38.         return a
  39.     }
  40.     return b
  41. }
////压缩二维数组 ，01🎒，时间 lmn ;空间 mn
func findMaxForm(strs []string, m int, n int) int {
    l := len(strs)
    dp := make([][]int, m+1)

    for k := range dp {
        dp[k] = make([]int, n+1)
    }


    for i := 1; i <= l; i++ {
        count := countZeroAndOne(strs[i-1])

        for j := m; j >= 0; j-- {                    // 为了不覆盖需要用到的上一层的状态值
            for k := n; k >= 0; k-- {
                if count[0] > j || count[1] > k {
                    dp[j][k] = dp[j][k]
                } else {
                    dp[j][k] = max(dp[j][k], dp[j-count[0]][k-count[1]]+1)
                }
            }
        }
    }
    return dp[m][n]
}

func countZeroAndOne(s string) []int {
    c := make([]int, 2)
    for i := 0; i < len(s); i++ {
        c[s[i]-'0']++
    }
    return c
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}