package com.fishercoder.solutions;

public class _474 {
    public static class Solution1 {
        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m + 1][n + 1];
            for (String str : strs) {
                int[] count = count(str);
                for (int i = m; i >= count[0]; i--) {
                    for (int j = n; j >= count[1]; j--) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
                    }
                }
            }
            return dp[m][n];
        }

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

}

@@ -85,16 +85,811 @@
 tion1 %7B%0A
+        /**%0A         * credit: https://leetcode.com/problems/ones-and-zeroes/discuss/95811/Java-Iterative-DP-Solution-O(mn)-Space and%0A         * https://leetcode.com/problems/ones-and-zeroes/discuss/95811/Java-Iterative-DP-Solution-O(mn)-Space/100352%0A         * %3Cp%3E%0A         * The problem can be interpreted as:%0A         * What's the max number of str can we pick from strs with limitation of m %220%22s and n %221%22s.%0A         *%0A         * Thus we can define dp%5Bi%5D%5Bj%5D as it stands for max number of str can we pick from strs with limitation of i %220%22s and j %221%22s.%0A         *%0A         * For each str, assume it has a %220%22s and b %221%22s, we update the dp array iteratively%0A         * and set dp%5Bi%5D%5Bj%5D = Math.max(dp%5Bi%5D%5Bj%5D, dp%5Bi - a%5D%5Bj - b%5D + 1).%0A         * So at the end, dp%5Bm%5D%5Bn%5D is the answer.%0A         */%0A
         

refactor 474