一、题目

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

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

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

点击查看原题

二、思路

1）动态规划

最多有m个0和n个1的最大子集，无法使用排序的方法，也无法使用贪心直接求解，因为有两个度量，0和1的个数，故使用动态规划进行求解。
由于有字符串个数、0的个数和1个的个数，这三个量，故而使用三维动态数组进行求解（01背包问题的一个升级版本），设立dp[i][j][k]代表使用i个字符串中，最多j个0和k个1的最大子集的值。假设strs[i]字符串有zeroCnt个0和oneCnt个1，有状态转移方程为：

其中，p[i-1][j-zeroCnt][k-oneCnt]代表的是：如果把strs[i]加入子集中，找到的能够加入strs[i]的最大子集数。

2）优化时间和空间复杂度

优化点一：
观察状态转移方程可以看出，方程当前状态，只跟i-1的状态有关，所以可以优化第一个维度。
优化点二：
当优化点一进行优化后，可以发现，使用一个m*n维的数组可以表示当前的状态转移方程，所有的值已经被初始化为i-1状态的值；这样就不需要把整个数组都扫描一遍进行赋值，只需要扫描j>=zeroCnt和k>=oneCnt的部分。

三、代码

1）动态规划

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int i = 1; i <= strs.length; i++) {
            int[] cnts = getCount(strs[i-1]);    // 获取该条字符串0和1的个数
            int zeroCnt = cnts[0], oneCnt = cnts[1];
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];    // 初始化dp[i][j][k]
                    if (j >= zeroCnt && k >= oneCnt) {
                        dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeroCnt][k-oneCnt] + 1);
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }
    private int[] getCount(String s) {
        int[] cnts = new int[2];
        for (char c : s.toCharArray()) {
            cnts[c - '0']++;
        }
        return cnts;
    }
}

时间复杂度为O(strs.lengthmn)，空间复杂度为O(strs.lengthmn)。

2）优化时间和空间复杂度

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < strs.length; i++) {
            int[] cnts = getCount(strs[i]);
            int zeroCnt = cnts[0], oneCnt = cnts[1];
            for (int j = m; j >= zeroCnt; j--) {    // 从高位向低更新，是因为需要用到低位i-1的状态值
                for (int k = n; k >= oneCnt; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j-zeroCnt][k-oneCnt] + 1);
                }
            }
        }
        return dp[m][n];
    }
    private int[] getCount(String s) {
        int[] cnts = new int[2];
        for (char c : s.toCharArray()) {
            cnts[c - '0']++;
        }
        return cnts;
    }
}

时间复杂度为O(strs.lengthmn)，空间复杂度为O(m*n)。