LeetCode 474. Ones and Zeroes

问题描述

• Example 1 :

Input: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

• Example 2 :

Input: Array = {“10”, “0”, “1”}, m = 1, n = 1
Output: 2
Explanation: You could form “10”, but then you’d have nothing left. Better form “0” and “1”.

• 地址

问题分析

• 该题是从字符串集合中选出若干字符串，保证选出的字符串的0，1总个数不超过给定值，求出最多能选出多少个字符串。
• 很明显，这和背包问题很像，只不过背包问题限制的是总重量，求获取价值的最大值。而该题有两个限制，0的个数和1的个数，求的是最多能选出多少字符串。类似于背包问题中问最多背几个所以，背包问题如果初始是个二维问题，那么该问题初始是一个三维dp问题。
• LeetCode dicuss里有背包和该题的具具体对比与详解: C++ DP Knapsack Approach
• 状态定义：
  
  • 背包问题： dp[i][j] : 表示在前 i 个物品中，选取最多加起来重量为j 的若干物品，得到的最大收益
  • 该题： dp[zero][one][k] : 在前k个字符串中，最多用zero个0，最多用one个1，能最多凑出多少个字符串
• 状态转移：
  
  • 背包问题：选不选第i个元素， dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + val[i - 1]) ，要保证 j - weight[i - 1] >= 0
  • 该题： 选不选第i个字符串，假设第 i个字符串的 0的数目为zeroNum, 1的数目为oneNum,那么 dp[zero][one][k] = Math.max(dp[zero][one][k - 1], 1 + dp[zero - zeroNum][one - oneNum][k - 1]),要保证zero >= zeroNum && one >= oneNum
• 背包问题可以优化为一维空间，同样该题也可以优化为二维空间。

经验教训

• 注意该题与背包问题的区别与联系
• 注意背包和该题， 与 LeetCode 322. Coin Change 凑硬币问题的区别，背包问题的限制是包的重量，包可以装不满，同样，该题 0和1也可以用不光，而凑硬币问题的限制是 想要凑的金额，必须要正好达到金额！不能多也不能少。
• 从三维到二维的空间优化，注意填表顺序的确定

代码实现

• 初始动态规划，三维

    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || (m == 0 && n == 0)) {
            return 0;
        }
        //dp[zero][one][k]在前k个字符串中，用zero个0，one个1，能最多凑出多少个字符串
        int[][][] dp = new int[m + 1][n + 1][strs.length + 1];
        for (int k = 1; k < strs.length + 1; ++k) {
            int zeroNum = 0;
            int oneNum = 0;
            char[] chs = strs[k - 1].toCharArray();
            for (char ch : chs) {
                if (ch == '0') {
                    ++zeroNum;
                }else {
                    ++oneNum;
                }
            }
            for (int zero = 0; zero <= m; ++zero ) {
                for (int one = 0; one <= n; ++one) {
                    //在用不用第k个字符串中，选取最多的一种情况
                    dp[zero][one][k] = dp[zero][one][k - 1];
                    if (one >= oneNum && zero >= zeroNum) {
                        dp[zero][one][k] = Math.max(dp[zero][one][k], 1 + dp[zero - zeroNum][one - oneNum][k - 1]);
                    }
                }
            }
        }
        return dp[m][n][strs.length];
    }

• 优化动态规划，二维

    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || (m == 0 && n == 0)) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int k = 1; k < strs.length + 1; ++k) {
            int zeroNum = 0;
            int oneNum = 0;
            char[] chs = strs[k - 1].toCharArray();
            for (char ch : chs) {
                if (ch == '0') {
                    ++zeroNum;
                }else {
                    ++oneNum;
                }
            }
            //注意此处的更新顺序，防止覆盖
            for (int zero = m; zero >= zeroNum; --zero) {
                for (int one = n; one >= oneNum; --one) {
                    dp[zero][one] = Math.max(dp[zero][one], 1 + dp[zero - zeroNum][one - oneNum]);
                }
            }
        }
        return dp[m][n];
    }