Ones and Zeroes

https://leetcode.com/problems/ones-and-zeroes/description/

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator ofm0sandn1srespectively. On the other hand, there is an array with strings consisting of only0sand1s.

Now your task is to find the maximum number of strings that you can form with givenm0sandn1s. Each0and1can be used at mostonce.

Thoughts

看到按序挑选并且每件物品最多只挑一次以求填满自然想到背包。与传统背包不同的是这里有两件物品要挑，于是用到三维数组。而且它要返回的是能填满的可能个数，不只是否能填满，因此还需要记录个数。让f[i][j][k]表示前i个数能填满j个0和k个1的最长长度。

Code

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] f = new int[len + 1][m + 1][n + 1];
        int[][] s = new int[strs.length + 1][2];
        for (int i = 0; i < len; i++) {
            int sum0 = 0;
            int sum1 = 0;
            for (int j = 0; j < strs[i].length(); j++) {
                if (strs[i].charAt(j) == '0') {
                    sum0++;
                } else {
                    sum1++;
                }
            }
            s[i + 1][0] = sum0;
            s[i + 1][1] = sum1;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    f[i][j][k] = f[i - 1][j][k];
                    if (j >= s[i][0] && k >= s[i][1]) {
                        f[i][j][k] = Math.max(f[i - 1][j][k], f[i - 1][j - s[i][0]][k - s[i][1]] + 1); 
                    }
                    //System.out.println(i + ", " + j +  ", " + k + ": " + f[i][j][k]);
                }
            }
        }

        return f[len][m][n];
    }
}

Analysis

Errors:

1. j和k的初始值要从0开始。不能从s[i][0]和s[i][1]开始。因为记录的不是当前是否能填满，而是能填满的最长长度，即使当前str不能用于填满，它的长度也至少是f[i-1][j][k]. 同样不能从1开始，因为像[0][1]这样很重要的情况没有考虑，不像二维只要考虑[0]就可以了。

三重循环，时间复杂度是O(lmn).

Ver.2

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] f = new int[m + 1][n + 1];

        for (String str : strs) {
            int zs = 0, os = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '0') {
                    zs++;
                } else {
                    os++;
                }
            }
            for (int i = m; i >= zs; i--) {
                for (int j = n; j >= os; j--) {
                    f[i][j] = Math.max(f[i][j], f[i - zs][j - os] + 1);
                }
            }
        }

        return f[m][n];
    }
}