LeetCode474. 一和零

题目解释：用 m 个0 和 n 个1，最多可以组成数组中的多少个01串？

　　　　示例2之所以不能是 “10”,原因是虽然1个0和1个1可以组成“10”，但只组成了数组中的1个元素，不是最大的。

☆☆☆☆思路：本题是二维的0-1背包问题，把总共的 0 和 1 的个数视为背包的容量

　　0-1背包，即数组中的元素不可重复使用。技巧为 nums放在外循环，target在内循环，且内循环倒序。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        /*int len = strs.length;
        // dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        for (int i = 1; i <= len; i++) {
            // 注意 有一位的偏移
            int[] cnt = countZeroAndOne(strs[i-1]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    int zeros = cnt[0];
                    int ones = cnt[1];
                    if (j >= zeros && k >= ones) {
                        // 要加1，因为目标值是能放进背包值的字符串的数量
                        dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];*/
        /**
         *  空间压缩， 从右往左算
         */
        int len = strs.length;
        int[][] dp = new int[m + 1][n + 1];

        for (String str : strs) {
            int[] cnt = countZeroAndOne(str);
            for (int j = m; j >= cnt[0]; j--) {
                for (int k = n; k >= cnt[1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - cnt[0]][k - cnt[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
    private int[] countZeroAndOne(String str) {
        int[] cnt = new int[2];
        for (char c : str.toCharArray()) {
            cnt[c - '0'] ++;
        }
        return cnt;
    }
}