Ones and Zeroes

题目
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 of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

答案

class Solution {
    // input 10 0 1
    // a     1  0 1
    // b     1  1 0
    // 前i个string里面，用j个0，k个1，最多可以形成多少个string(背包问题，可以想象成最多可以拿多少个重量为j，体积为k的物品)
    // f[i][j][k] = if not taking i-1 th string, f[i - 1][j][k]
    //            = if taking i-1 th string, f[i - 1][j - a[i - 1]][k - b[i - 1]]
    // take the max of the two right hand side above 
    public int number0s(String s) {
        int cnt = 0;
        for(int i = 0; i < s.length(); i++) if(s.charAt(i) == '0') cnt++;
        return cnt;
    }
    public int findMaxForm(String[] strs, int M, int N) {
        int[] a = new int[strs.length];
        int[] b = new int[strs.length];
        
        int n = strs.length, max = 0;
        // First compute array a and b(a[i]: how many 0's in strs[i], b is similar but for 1's).
        for(int i = 0; i < strs.length; i++) {
            a[i] = number0s(strs[i]);
            b[i] = strs[i].length() - a[i];
        }
        
        int[][][] f = new int[n + 1][M + 1][N + 1];
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= M; j++) {
                for(int k = 0; k <= N; k++) {
                    if(i == 0) {
                        f[i][j][k] = 0;
                        continue;
                    }
                    f[i][j][k] = f[i - 1][j][k];
                    if(j >= a[i - 1] && k >= b[i - 1]) {
                        f[i][j][k] = Math.max(f[i][j][k], 1 + f[i - 1][j - a[i - 1]][k - b[i - 1]]);
                    }
                    max = Math.max(max, f[i][j][k]);
                }
            }
        }
        return max;
    }
}