问题描述
You are given an array of binary strings strs and two integers m and n.
Return the size of the largest subset of strs such that there are at most m 0’s and n 1’s in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
Example 1:
Input: strs = [“10”,“0001”,“111001”,“1”,“0”], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0’s and 3 1’s is {“10”, “0001”, “1”, “0”}, so the answer is 4.
Other valid but smaller subsets include {“0001”, “1”} and {“10”, “1”, “0”}.
{“111001”} is an invalid subset because it contains 4 1’s, greater than the maximum of 3.
Example 2:
Input: strs = [“10”,“0”,“1”], m = 1, n = 1
Output: 2
Explanation: The largest subset is {“0”, “1”}, so the answer is 2.
Constraints:
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] consists only of digits ‘0’ and ‘1’.
- 1 <= m, n <= 100
问题分析
依然是dp方式去尝试解决
首先，最容易想到的brute force的方式就是：
- 维护一个全局的最大值，初始为0；
- 对于strs里的每一个字符串，如果选用了，那么可能的解就为 从strs中移除当前字符串，m和n也相应移除当前字符串的0和1的数量之后的最优解 加上 1, 即 f(strs, m, n) = max(f(strs-strs[0], m-x0, n-y0), f(strs-strs[1], m-x1, n-y1), …)
- 在以上递归调用过程中，更新最大值即可
代码如下：
初始解法1
func findMaxForm(strs []string, m int, n int) int {
if len(strs) == 1 {
ones := countOne(strs[0])
zeroes := len(strs[0]) - ones
if zeroes > m || ones > n {
return 0
}
return 1
}
ans := 0
for i := 0; i < len(strs); i++ {
ones := countOne(strs[i])
zeroes := len(strs[i]) - ones
if m-zeroes < 0 || n-ones < 0 {
continue
}
tmpans := 1 + findMaxForm(append(strs[0:i], strs[i+1:]...), m-zeroes, n-ones)
if tmpans > ans {
ans = tmpans
}
}
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func countOne(str string) int {
ans := 0
for _, v := range str {
if v == '1' {
ans++
}
}
return ans
}
初始解法2
很明显，最初的解法会存在很多的重复计算过程，导致时间复杂度偏高。所以我们要想办法降低重复计算量，dp中常用的方式就是记忆化处理，即保存计算的中间结果。
为此， 我们定义一个dp[i][j][k]，表示从strs的第i个位置开始，0的最大数量为j，1的最大数量为k的最大子集长度。 计算过程中，每计算出一个结果，都存入该dp；后续计算中，如果发现已经计算过，则直接返回。
代码如下(该代码可AC，但是运行时间在100ms往上)：
func findMaxFormV2(strs []string, m int, n int) int {
donemap := [][][]int{}
for i := 0; i <= len(strs); i++ {
t := [][]int{}
for j := 0; j <= m; j++ {
tmp := []int{}
for k := 0; k <= n; k++ {
tmp = append(tmp, -1)
}
t = append(t, tmp)
}
donemap = append(donemap, t)
}
return find(strs, 0, m, n, donemap)
}
func find(strs []string, startPos int, m int, n int, donemap [][][]int) int {
if donemap[startPos][m][n] != -1 {
return donemap[startPos][m][n]
}
ones := countOne(strs[startPos])
zeroes := len(strs[startPos]) - ones
if len(strs[startPos:]) == 1 {
if zeroes > m || ones > n {
donemap[startPos][m][n] = 0
return 0
}
donemap[startPos][m][n] = 1
return 1
}
if m >= zeroes && n >= ones {
ans := max(find(strs, startPos+1, m-zeroes, n-ones, donemap)+1, find(strs, startPos+1, m, n, donemap))
donemap[startPos][m][n] = ans
return ans
}
ans := find(strs, startPos+1, m, n, donemap)
donemap[startPos][m][n] = ans
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func countOne(str string) int {
ans := 0
for _, v := range str {
if v == '1' {
ans++
}
}
return ans
}
优化解法
最后，仍然是讨论区的优化解法，也是dp，只不过定义的更为简洁，且时间复杂度仅为O(kl+kmn)，k是strs长度，l为strs中字符串的平均长度。
这里，dp的定义为：dp[i][j]表示至多i个0，j个1的限制条件下的最大子集长度；那么，dp[m][n]即为最终所求
对于每一个strs中的字符串，都有2种选择：
- 选用: dp[i][j] = dp[i-zeroes][j-ones]+1
- 不选用: dp[i][j]维持不变
综上， dp[i][j] = max(dp[i-zeroes][j-ones]+1, dp[i][j])
这里dp定义很容易理解，但是计算过程有点费解，我的理解是：
如果strs中只考虑第一个字符串，那么显然dp[m][n]，对于m>=zeros, n>=ones，都需要更新为最优解1
此时，再考虑加入第二个字符串，那么同样，对于dp[m][n]，在考虑第二个字符串是否选用后，继续更新dp数组
以此类推，直至所有字符串被全部纳入计算，dp[m][n]也最终更新完毕。此时的dp[m][n]即为所求。
func findMaxFormV3(strs []string, m int, n int) int {
dp := [][]int{}
for i := 0; i <= m; i++ {
dp = append(dp, make([]int, n+1))
}
for _, v := range strs {
ones := countOne(v)
zeroes := len(v) - ones
for i := m; i >= zeroes; i-- {
for j := n; j >= ones; j-- {
dp[i][j] = max(dp[i-zeroes][j-ones]+1, dp[i][j])
}
}
}
return dp[m][n]
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func countOne(str string) int {
ans := 0
for _, v := range str {
if v == '1' {
ans++
}
}
return ans
}
v1.5.2