474. Ones and Zeroes

 You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

 

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

 

Constraints:

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

Answer:

class Solution {
    /**
    *To better understand, DP[][] can be rewrite as DP[][][], 
    *e.g. DP[0][i][j] = 0 means when the string array is empty, 
    *we can not form any string. Then we put the first element of strs in our pool,
    *and we can write DP[1][i][j]=Math.max(DP[0][i][j], 1+DP[0][i-c[0]][j-c[1]]);
    *(for each i and j). Actually, we find that each time we add one more string k,
    *DP[k][i][j]=Math.max(DP[k-1][i][j], 1+DP[k-1][i-c[0]][j-c[1]]). 
    *Since each i and j will not be influenced by higher i,j, 
    * and DP[k-1] will not be used in the future, 
    * we can iterate backward and update DP[i][j] in place. 
    * In the end, we return DP[m][n] which is actually DP[strs.length][m][n].
    *
    **/
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs.length==0) return 0;
        int[][] DP=new int[m+1][n+1];
        for(String str:strs){
            int[] c=count(str);
            for(int i=m;i>=c[0];i--){
                for(int j=n;j>=c[1];j--){
                    DP[i][j]=Math.max(DP[i][j], 1+DP[i-c[0]][j-c[1]]);
                }
            }
        }
        return DP[m][n];

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

My Summary: the key points here are: 

1. since there could be multiple combinations as result meeting requirements, the best solution is very likely to be using DP

2. DP solution's key point is to figure out the X/Y Axis, and the relation between DP[X(k)i][X(k)j] and DP[X(k+1)i][X(k+1)j], Xk and X(k+1) is element in original array and its following element.