# 474 Ones and Zeroes

給一個List，裡面都是由0和1組成的String，給正整數m表示0的個數，正整數n表示1的個數。

問有m個0,n個1的限制下，最多可以組成幾個list裡面的String?

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: There are 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Concept 用一二維陣列dp[i][j]表示i個0和j個1時可以組成幾個String。 用for loop走過Array中的每個String， 該String中0的數量為numZeroes，1的數量為numOnes， 把dp[][]中i,j大於numZeroes和numOnes的格子都更新， 更新方法：dp[i][j] = Math.max(dp[i][j], dp[i - numZeroes][j - numOnes] + 1); dp[i-numZeroes][j-numOnes]的意義就是還沒選當下的這個String，+1就表示選了當下的這個String。 最後dp[m][n]為結果。

Code

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        int numZeroes, numOnes;
        for(String s : strs){
            numZeroes = numOnes = 0;
            for(char c : s.toCharArray()){
                if(c=='0')  numZeroes++;
                else if(c=='1') numOnes++;
            }

            for (int i = m; i >= numZeroes; i--) {
                for (int j = n; j >= numOnes; j--) {
                      dp[i][j] = Math.max(dp[i][j], dp[i - numZeroes][j - numOnes] + 1);
                }
            }
        }

        return dp[m][n];
    }
}