一和零

题目

思路

• 暴力递归：当字符串所要求的0和1小于等于当前剩余m和n，我们可以对该字符进行选用或不选用，大于时不选用该字符串，直接暴力这几种情况，选出最大可能性的。等价于背包问题
• 备忘录：由于递归会超时，因为有许多重复分支，可以用容器记录下来
• 动态规划：状态转移就是暴力递归中的可能性，dp数组要用三维表示，dp[插入/不插入第i个字符串][m个1][n个0] 组合最多的字符串数量
• 优化动态规划的dp数组，通过画图很容易发现，对于二维来说，如果每次更新数组只依赖于前一维以及单独其他个别数据，这种是可以优化为一维数组，对于三维来说，如果每次更新数组依赖前二维数组，那么这个三维可以优化为二维

代码

    1.暴力递归回溯超时
    public int findMaxForm(String[] strs, int m, int n) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : strs) {
            int zero = 0, one = 0;
            for (int i = 0; i < s.length(); i++) {
                if ('0' == s.charAt(i)) zero++;
                if ('1' == s.charAt(i)) one++;
            }
            String key = zero + "-" + one;
            int count = map.getOrDefault(key, 0) + 1;
            map.put(key, count);
        }
        return  recur(map, m, n);
    }
    public int recur(Map<String, Integer> map, int m, int n) {
        if (m == 0 && n == 0) return 0;
         int max = 0;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                String key = i + "-" + j;
                if (!map.containsKey(key) || map.get(key) <= 0) continue;
                int count = map.get(key);
                int k = count == 0 ? 0 : 1;
                if (count > 0) map.put(key, count - 1);
                max = Math.max(max, recur(map, m - i, n - j) + k);
                if (count > 0) map.put(key, count);
            }
        }
        return max;
    }
    //1. 暴力回溯超时
    public int findMaxForm(String[] strs, int m, int n) {
       boolean[] flag = new boolean[strs.length];
       return recur(strs, flag, m, n);
    }
    Map<String, Integer> map = new HashMap<>();
    public int recur(String[] strs, boolean[] flag, int m, int n) {
        if (m == 0 && n == 0) return 0;
        if (m < 0 || n < 0) return -1;
        int max = 0;
        for (int j = 0; j < strs.length; j++) {
            if (flag[j]) continue;
            int zero = 0, one = 0;
            for (int i = 0; i < strs[j].length(); i++) {
                if ('0' == strs[j].charAt(i)) zero++;
                else one++;
            }
            flag[j] = true;
            max = Math.max(max, recur(strs, flag, m - zero, n - one) + 1);
            flag[j] = false;
        }
        return max;
    }
    1.暴力递归超时
    public int findMaxForm(String[] strs, int m, int n) {
       return recur(strs, 0, m, n);
    }
    public int recur(String[] strs, int index, int m, int n) {
        if (index >= strs.length) return 0;
        int zero = 0, one = 0;
        for (int i = 0; i < strs[index].length(); i++) {
            if ('0' == strs[index].charAt(i)) 
                zero++;
            else 
                one++;
        }
        if (m - zero >= 0 && n - one >= 0) 
            return Math.max(recur(strs, index + 1, m, n), 
                        recur(strs, index + 1, m - zero, n - one) + 1);
        else 
            return recur(strs, index + 1, m, n);
    }
    2.备忘录
    public int findMaxForm(String[] strs, int m, int n) {
       return recur(strs, 0, m, n);
    }
    Map<String ,Integer> map = new HashMap<>();
    public int recur(String[] strs, int index, int m, int n) {
        if (index >= strs.length) return 0;
        String key = index + "-" + m + "-" + n; 
        if (map.containsKey(key)) return map.get(key);
        int zero = 0, one = 0, res = 0;
        for (int i = 0; i < strs[index].length(); i++) {
            if ('0' == strs[index].charAt(i)) 
                zero++;
            else 
                one++;
        }
        if (m >= zero && n >= one) 
            res =  Math.max(
                        recur(strs, index + 1, m, n), 
                        recur(strs, index + 1, m - zero, n - one) + 1);
        else 
            res = recur(strs, index + 1, m, n);
        map.put(key, res);
        return res;
    }
    3. 动态规划，三维dp数组可以看做是一个长方体
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[插入/不插入第i个字符串][m个1][n个0] 组合最多的字符串数量
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int k = 1; k <= strs.length; k++) {
            String s = strs[k - 1];
            int zero = 0, one = 0;
            for (int i = 0; i < s.length(); i++) {
                if ('0' == s.charAt(i))
                    zero++;
                else 
                    one++;
            }
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (i >= zero && j >= one) 
                     dp[k][i][j] = Math.max(dp[k - 1][i][j], dp[k - 1][i - zero][j - one] + 1);
                    else 
                     dp[k][i][j] = dp[k - 1][i][j];
                }
            }
        }
        return dp[strs.length][m][n];
    }
    //4.优化dp数组,我们看到每次只是用到了上一层的长方形的面，因此可以转换为二维数组
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int zero = 0, one = 0;
            for (int i = 0; i < s.length(); i++) {
                if ('0' == s.charAt(i)) zero++;
                else one++;
            }
            for (int i = m; i >= zero; i--) {
                for (int j = n ; j >= one; j--) {
                    dp[i][j] = Math.max(dp[i - zero][j - one] + 1, dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }

一和零