一和零

难度: Medium

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

Submission

运行时间: 61 ms

内存: 16.3 MB

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        d = [[0 for _ in range(n+1)] for _ in range(m+1)]
        # ms = [len([1 for xi in x if xi == '0']) for x in strs]
        # ns = [len([1 for xi in x if xi == '1']) for x in strs]
        
        mn = [(len([1 for xi in x if xi == '0']), len([1 for xi in x if xi == '1'])) for x in strs]
        mn.sort(key = lambda x: x[0])
        d = [[m, 0] for _ in range(n+1)]
        for i in range(len(mn)):  # 起点不要把没词i=0放进来
            # # 这样就慢 因为很多到不了的位置
            # for m0 in range(m, ms[i-1]-1, -1):  # 复用，所以要从后往前
            #     for n0 in range(n, ns[i-1]-1, -1):  #  不选用当前词就是直接保留不更新值，所以没必要处理，只处理需要判断的,快四五百秒
            #         if d[m0-ms[i-1]][n0-ns[i-1]] > d[m0][n0]-1:
            #             d[m0][n0] = d[m0-ms[i-1]][n0-ns[i-1]] + 1  # 加新词，+1

            # for m0 in range(m-ms[i]+1)[::-1]:  # 复用，所以要从后往前
            #     for n0 in range(n-ns[i]+1)[::-1]:  #  不选用当前词就是直接保留不更新值，所以没必要处理，只处理需要判断的,快四五百秒
            #         if d[m0][n0] > d[m0+ms[i]][n0+ns[i]]-1:
            #             d[m0+ms[i]][n0+ns[i]] = d[m0][n0] + 1  # 加新词，+1

            # 如果先按0从小到大排好，就可以不用记录全部0的情形了，因为当前词一定是在未遍历的词中，使1数量增大mn[1]时，0数量增加最少的词
            # 保证了当前是能达到的最优选择
            if mn[i][0] > m: break
            if mn[i][1] > n:continue
            for ni in range(n, mn[i][1]-1, -1):
                if d[ni][1] < d[ni-mn[i][1]][1] + 1 and d[ni-mn[i][1]][0] >= mn[i][0]:
                    d[ni][1] = d[ni-mn[i][1]][1] + 1
                    d[ni][0] = d[ni-mn[i][1]][0] - mn[i][0]
        res = 0
        for i in d:
            if res < i[1]:
                res = i[1]
        return res

Explain

这个题解使用动态规划的思路来解决问题。首先将字符串数组 strs 中的每个字符串统计出其中 0 和 1 的个数，并将结果保存在 mn 数组中。然后对 mn 数组按照 0 的个数从小到大进行排序。接下来使用一个二维数组 d 来记录动态规划的状态，其中 d[i][0] 表示当前能够达到的最小的 0 的个数，d[i][1] 表示在 d[i][0] 个 0 的情况下，最多能够包含的 1 的个数。遍历 mn 数组，对于每个字符串，更新 d 数组的状态。最后遍历 d 数组，找出最大的 d[i][1] 作为最终结果返回。

时间复杂度: O(mn + nlogn)

空间复杂度: O(mn)

```python
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 统计每个字符串中 0 和 1 的个数
        mn = [(len([1 for xi in x if xi == '0']), len([1 for xi in x if xi == '1'])) for x in strs]
        # 按照 0 的个数从小到大排序
        mn.sort(key = lambda x: x[0])
        # 初始化动态规划数组
        d = [[m, 0] for _ in range(n+1)]
        for i in range(len(mn)):  # 遍历每个字符串
            if mn[i][0] > m: break  # 如果当前字符串的 0 的个数大于 m，则无法选择，直接跳出循环
            if mn[i][1] > n: continue  # 如果当前字符串的 1 的个数大于 n，则无法选择，继续下一个字符串
            for ni in range(n, mn[i][1]-1, -1):  # 从后往前遍历 1 的个数
                # 如果选择当前字符串能够获得更多的 1，并且选择后 0 的个数不超过 m，则进行状态更新
                if d[ni][1] < d[ni-mn[i][1]][1] + 1 and d[ni-mn[i][1]][0] >= mn[i][0]:
                    d[ni][1] = d[ni-mn[i][1]][1] + 1
                    d[ni][0] = d[ni-mn[i][1]][0] - mn[i][0]
        # 遍历 d 数组，找出最大的 d[i][1] 作为结果返回
        res = 0
        for i in d:
            if res < i[1]:
                res = i[1]
        return res
```

Explore

将mn数组按照0的个数从小到大排序有助于优先处理使用较少0的字符串。这种策略在动态规划中是有益的，因为它允许我们在不超过m的限制下尽可能地包含更多的字符串。这样的排序确保了在遍历字符串的过程中，我们可以先尝试添加对资源消耗较低的字符串，这可能增加在不超过m和n限制的情况下可以选择的字符串总数。

在动态规划中，每一步的状态更新都是基于之前的最优解进行计算的。通过维护d[i][0]作为当前可用的最小0的个数和d[i][1]作为在这种0的消耗下可获得的最大1的数量，我们确保在每一步都考虑了到达当前状态的最佳路径。这种设置允许我们在每一步决策时，都是基于当前可用的最优资源配置来进行更新，从而确保整个过程的每一步都是局部最优解，进而推导出全局最优解。

在动态规划中从后往前更新的主要目的是为了防止在更新过程中覆盖还未使用到的状态。这是因为每个状态的更新可能依赖于当前阶段的其他状态，如果从前向后更新，那么可能会导致某些状态被早期的更新错误地覆盖，从而影响最终结果的正确性。通过从后往前更新，我们可以确保在更新当前状态时，依赖的状态仍然是在这一轮更新之前的状态，从而保持更新的正确性。

这个条件判断确实意味着如果某个字符串的0的数量超过m，那么这个字符串及所有排序后的后续字符串都不会被考虑，因为它们的0的数量只会更多。这种处理方式基于mn数组已经按照0的数量排序的前提，确保了一旦某个字符串的0数量超过了m，后续的字符串也同样不可能被包含在任何有效的组合中（因为它们需要的0的数量更多）。因此，这种处理方式并不会遗漏有效的字符串组合，而是一种效率上的优化。