题目描述

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

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

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

样例

输入：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。

输入：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

算法

(动态规划，01背包) $O(k(l + mn))$

1. 典型的二维 01 背包问题，每个字符串看做物品，代价是字符 0 和 1 的个数，价值为 1。
2. 设 $f(t, i, j)$ 表示考虑了前 $t$ 个物品（字符串），使用 $i$ 个 0 和 $j$ 个 1 所能得到最大价值，根据每个字符串 0 和 1 的个数，进行枚举转移。

时间复杂度

• 假设总共 $k$ 个字符串，每个字符串的长度为 $l$。
• 遍历字符串需要 $O(l)$ 的时间。
• 动态规划的状态数为 $O(kmn)$，转移时间为常数，故动态规划的时间复杂度为 $O(kmn)$。
• 总时间复杂度为 $O(k(l + mn))$。

空间复杂度

• 背包采用了空间优化，所以仅需要额外 $O(mn)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));

        for (string &str : strs) {
            int cm = 0, cn = 0;

            for (char &c : str) {
                if (c == '0') cm++;
                else cn++;
            }

            for (int i = m; i >= cm; i--)
                for (int j = n; j >= cn; j--)
                    f[i][j] = max(f[i][j], f[i - cm][j - cn] + 1);
        }

        return f[m][n];
    }
};