leetcode-ones-zeros

题目大意

　　https://leetcode.com/problems/ones-and-zeroes/

　　给你字符串数组，假设你有m个字符0和n个字符1，问你能够最多包含数组中的字符串，只论数量的最大值。

题目分析

　　典型的动态规划，下面给出记忆化搜索实现和动态规划实现，注意动态规划要利用滚动数组优化到二维。

代码

　　记忆化搜索：

public class Solution {
    private int[][][] f;
    private int[] l0;
    private int[] l1;
    
    private int search(String[] strs, int m, int n, int idx) {
        int len = strs.length;
        if (m <= 0 && n <= 0) {
            return 0;
        }
        if (m < 0) {
            m = 0;
        }
        if (n < 0) {
            n = 0;
        }
        if (idx > len - 1) {
            return 0;
        }
        if (f[idx][m][n] > 0) {
            return f[idx][m][n];
        }
        // choose idx
        int v1 = 0;
        if (m >= l0[idx] && n >= l1[idx]) {
            v1 = 1 + search(strs, m - l0[idx], n - l1[idx], idx + 1);
        }
        // do not choose idx
        int v2 = search(strs, m, n, idx + 1);
        f[idx][m][n] = Math.max(v1, v2);
        return f[idx][m][n];
    }
    
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) {
            return 0;
        }
        int len = strs.length;
        f = new int[len][m + 1][n + 1];
        l0 = new int[len];
        l1 = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    f[i][j][k] = -1;
                }
            }
        }
        //init l0,l1
        for (int i = 0; i < len; i++) {
            String s = strs[i];
            int len2 = s.length();
            int a = 0;
            int b = 0;
            for (int j = 0; j < len2; j++) {
                if (s.charAt(j) == '0') {
                    a++;
                } else {
                    b++;
                }
            }
            l0[i] = a;
            l1[i] = b;
        }
        return search(strs, m, n, 0);
    }
}

　　动态规划，利用了滚动数组：

public class Solution {
    private int[][] f;
    private int[] l0;
    private int[] l1;
    
    private int dp(String[] strs, int m, int n) {
        int len = strs.length;
        // get f[j][k]
        for (int i = len - 1; i >= 0; i--) {
            for (int j = m; j >= 0; j--) {
                for (int k = n; k >= 0; k--) {
                    int v1 = 0;
                    if (j >= l0[i] && k >= l1[i]) {
                        v1 = (1 + f[j - l0[i]][k - l1[i]]);
                    }
                    f[j][k] = Math.max(v1, f[j][k]);
                }
            }
        }
        return f[m][n];
    }
    
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) {
            return 0;
        }
        int len = strs.length;
        f = new int[m + 1][n + 1];
        l0 = new int[len];
        l1 = new int[len];
        //init l0,l1
        for (int i = 0; i < len; i++) {
            String s = strs[i];
            int len2 = s.length();
            int a = 0;
            int b = 0;
            for (int j = 0; j < len2; j++) {
                if (s.charAt(j) == '0') {
                    a++;
                } else {
                    b++;
                }
            }
            l0[i] = a;
            l1[i] = b;
        }
        return dp(strs, m, n);
    }
}