LeetCode：一和零_474

定义状态：dp[i][m][n]表示0-i个物品，m个装1的背包，n个装0的背包可以装下多少个物品
状态转移方程：dp[i][m][n]=max(dp[i-1][m][n],dp[i-1][m-i1][n-i0]+1)
初始值：dp[0][m][n]=0

func findMaxFormOld(strs []string, m int, n int) int {
    dp := iniDpArr(strs, m, n)
    for i, str := range strs {
        zeroCount, oneCount := countOfZeroAndOne(str)
        // 当前物品固定，穷举背包数量
        for j := 0; j <= m; j++ {
            for k := 0; k <= n; k++ {
                // 装不下该物品 = 不装
                if j < zeroCount || k < oneCount {
                    dp[i+1][j][k] = dp[i][j][k]
                } else {
                    dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-zeroCount][k-oneCount]+1)
                }
            }
        }
    }
    return dp[len(strs)][m][n]
}

// 优化后
func findMaxForm(strs []string, m int, n int) int {
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for _, s := range strs {
        zeros := strings.Count(s, "0")
        ones := len(s) - zeros
        for j := m; j >= zeros; j-- {
            for k := n; k >= ones; k-- {
                dp[j][k] = max(dp[j][k], dp[j-zeros][k-ones]+1)
            }
        }
    }
    return dp[m][n]
}

func countOfZeroAndOne(str string) (int, int) {
    var zeroCount, oneCount int
    for _, char := range str {
        if '0' == char {
            zeroCount++
        } else if '1' == char {
            oneCount++
        }
    }
    return zeroCount, oneCount
}

func iniDpArr(strs []string, m int, n int) [][][]int {
    var dp = make([][][]int, len(strs)+1)
    for i := range dp {
        dp[i] = make([][]int, m+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, n+1)
        }
    }
    return dp
}

func max(i int, i2 int) int {
    if i > i2 {
        return i
    }
    return i2
}