一和零

题目:

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

思路

使用动态规划,求解.

首先创建一个三维数组dp[i][j][k],其中i代表strs前i个元素满足的个数,j代表了其中0为j时满足的个数,k位其中1为k时满足的个数

首先计算strs[0],也就是"10"中0和1的个数:得出zeros=0,ones=1

得出0,1的个数后

1. 迭代所有j,k可以满足m,n的情况

2. 首先拷贝上一个元素可以满足的情况

3. 然后判断如果j>=zero并且k>=one就进行重赋值

   1. 首先当j==zero && k==one的时候,这时dp[i][j][k]应该为1

   2. 当j>zero || k>one时,这时为dp[i-1][j-zero][k-one]+1和本身取最大值

      dp[i-1][j-zero][k-one]+1的意思:

      +1就是包括自己的意思,而dp[i-1][j-zero][k-one]就是说明当满足j >= zero && k >= one的时候,0和1的值已经比当前字符串里的多了,这时就可以从之前字符串中找到满足要求的

      之前满足0为j-zero,1为k-one的个数就是dp[i-1][j-zero][k-one]

      例子:

      ---

      比如"10",zero=1,one=1,i=1

      当j<zero || k<one时,满足的个数为dp[0][j][k],也就是默认值0

      而当j>=zero && k>=one时,dp[0][j-zero][k-zero]还是0,但+1后就是1了,所以为1

      ---

      比如"0001",zero=3,one=1,i=2

      当j<zero || k<one时,满足的个数为dp[1][j][k]

      而当j>=zero && k>=one时,dp[1][j-zero][k-zero]是1,但+1后就是2了,所以为2

代码

class Solution {
    public int findMaxForm(String[] str, int m, int n) {

        int[][][] dp = new int[str.length + 1][m + 1][n + 1];

        for (int i = 1; i <= str.length; ++i) {
            int[] count = countOneAndZero(str[i - 1]);
            int zero = count[0], one = count[1];
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= n; ++k) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= zero && k >= one) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j - zero][k - one] + 1);
                    }
                }
            }
        }
        return dp[str.length][m][n];
    }

    private int[] countOneAndZero(String str) {
        int[] res = new int[2];
        for (int i = 0; i < str.length(); ++i) {
            if (str.charAt(i) == '0') {
                ++res[0];
            } else {
                ++res[1];
            }
        }
        return res;
    }
}