LeetCode-474

题目

474. 一和零

结果

代码

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 _, str := range strs {
		zero, one := cnt(str)
		// 为什么从后往前：旧的dp[i][j]存储着截止上一次（还没有当前资源）的最佳值，这个递推公式描述的是有当前资源和没有当前资源两种情况的关系
		for i := m; i >= zero; i-- {
			for j := n; j >= one; j-- {
				dp[i][j] = max(dp[i][j], dp[i-zero][j-one]+1)
			}
		}
	}
	return dp[len(dp)-1][len(dp[0])-1]
}

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

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