474. 一和零

力扣链接(中等)：https://leetcode.cn/problems/ones-and-zeroes

给你一个二进制字符串数组 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

个人题解

建议先完成 416. 分割等和子集 后再完成本题。

二维 dp 滚动数组

根据题目，本题需要满足两个条件，0 的数量最多为 m，1 的数量最多为 n，那么转换为 01 背包就应该有两个装满条件，一个是装满 0，一个是装满 1，显然一维的 dp 数组无法解决这样的问题。

由此引出二维 dp 滚动数组，根据递推公式逐次覆盖上一层 dp 数组实现降低物品项这一维度，从而减少空间复杂度。如果不使用滚动数组降维，那么就应该是三维数组，其中物品项作为一维，0 和 1 的数量作为二维 weight。

类比一维 dp 滚动数组，可以发现 for 循环变成了三层，因为本题不仅要枚举物品项，还需要枚举 0 和 1 的数量，相当于一维 dp 滚动数组中内层 for 循环枚举了两个 weight。

动态规划（滚动数组）

1. dp[i][j] 表示由最多 i 个 0，j 个 1 组成的最大子集中有 dp[i][j] 个元素；
2. 递推公式 dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)，其中 zero 和 one 分别为当前枚举项中 0 和 1 的数量；
3. 初始化 dp 数组为 0 即可；
4. 遍历顺序参照 416. 分割等和子集 中对一维滚动 dp 数组的说明；
5. 手动推导 dp 数组无误。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        const int M = 100 + 10;
        const int N = 100 + 10;

        int dp[M][N] = {};

        for(auto item : strs) {
            int zero = 0, one = 0;

            // 统计数量
            for(auto c : item) {
                if(c == '0') zero++;
                else one++;
            }

            // 相当于一维 dp 滚动数组中的内层 for 循环
            // 注意遍历顺序是从后向前
            for(int i = m; i >= zero; i--) {
                for(int j = n; j >= one; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);
                }
            }
        }

        return dp[m][n];
    }
};