[数据结构与算法]【LeetCode】474. 一和零（错题2刷）

• 思路
  该子集中 最多 有 m 个 0 和 n 个 1 。返回的是最大子集长度。
  一种想法就暴力遍历，使用回溯法搜索出所有的情况，然后取一个最大的。只是采用暴力法应该会超时。
  这道题其实是有覆盖子问题的，即m = 5, n = 3是基于m = 4, n = 2及更小的直到1，因此考虑到动态规划的背包问题，然后本题子集中的元素只能用一次，所以是01背包问题，现在不同的是m和n它有两个背包容量，分别是0和1，字符串的0、1长度分别为物品的重量，即0和1各自的个数。
  定义：dp[m][n]，dp[i][j]表示i个0，j个1下的最大子集长度。
  dp的状态转移方程：这其实也是求组合的问题，dp[i][j] += dp[m - s_0_num][n - s_1_num]；
  dp的初始化：开到dp[i][j]依赖于前值，因此前值需要置为1，否则后面都是0，dp[0][0] = 1。
  推理了一下，发现有问题，参考题解
  整体思路是对的，的确是分为两个维度来计算。
  dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

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

func count(s string) (int, int) {
    num_0, num_1 := 0, 0
    for _, v := range s {
        if v == '0' {
            num_0++
        } else {
            num_1++
        }
    }
    return num_0, num_1
}

func findMaxForm(strs []string, m int, n int) int {
    // 1 <= m, n <= 100
    dp := make([][]int, m + 1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n + 1)
    }
    for i := 0; i < len(strs); i++ {
        num_0, num_1 := count(strs[i])
        for j := m; j >= num_0; j-- {
            for k := n; k >= num_1; k-- {
                dp[j][k] = max(dp[j][k], dp[j - num_0][k - num_1] + 1)
            }
        }
    }
    return dp[m][n]
}