474. Ones and Zeroes

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 定义 dp[i][j][k] 为从前 i 个字符串中选择 dp[i][j][k] 个字符串组成的子集最多含有 m 个 0 和 n 个 1
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];

        for (int i = 1; i <= strs.length; i++) {
            int[] weight = getWeight(strs[i - 1]);
            int zeroCount = weight[0], oneCount = weight[1];

            // 注意 j 和 k 要从 0 开始遍历，因为可能存在 0 个 0 或 0 个 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 - zeroCount >= 0 && k - oneCount >= 0) {
                        // 注意依赖的是 dp[i - 1][j - sm][k - sn] 而不是 dp[i][j - sm][k - sn]
                        dp[i][j][k] = Math.max(dp[i - 1][j - zeroCount][k - oneCount] + 1, dp[i - 1][j][k]);
                    }
                }
            }
        }

        return dp[strs.length][m][n];
    }

    private int[] getWeight(String str) {
        int zeroCount = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                zeroCount++;
            }
        }
        return new int[]{zeroCount, str.length() - zeroCount};
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= strs.length; i++) {
            int[] zeroOnes = getZeroOnes(strs[i - 1]);
            int zeroCount = zeroOnes[0], oneCount = zeroOnes[1];
            for (int j = m; j >= 0; j--) {
                for (int k = n; k >= 0; k--) {
                    if (zeroCount > j || oneCount > k) {
                        dp[j][k] = dp[j][k];
                    } else {
                        dp[j][k] = Math.max(dp[j][k], dp[j - zeroCount][k - oneCount] + 1);
                    }
                }
            }
        }

        return dp[m][n];
    }

    private int[] getZeroOnes(String str) {
        int[] zeroOnes = new int[2];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            zeroOnes[c - '0']++;
        }

        return zeroOnes;
    }
}

References

474. Ones and Zeroes