leetcode-go/leetcode/medium/474.ones-and-zeroes.go

func findMaxForm(strs []string, m int, n int) int {
	o := len(strs)
	dp := make([][][]int, m+1)
	for i := range dp {
		dp[i] = make([][]int, n+1)
		for j := range dp[i] {
			dp[i][j] = make([]int, o+1)
		}
	} // dp[i][j][k] = max(dp[i][j][k-1], dp[i-dm][j-dn][k-1] + 1)
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			for k := 1; k <= o; k++ {
				dm, dn := zeroAndOne(strs[k-1])
				if dm <= i && dn <= j {
					dp[i][j][k] = maxInt(dp[i][j][k-1], dp[i-dm][j-dn][k-1]+1)
				} else {
					dp[i][j][k] = dp[i][j][k-1] // Important!
				}
			}
		}
	}
	return dp[m][n][o]
}

func zeroAndOne(s string) (zero, one int) {
	for _, r := range s {
		if r == '0' {
			zero++
		} else if r == '1' {
			one++
		}
	}
	return
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}