1、前言

2、思路

将问题转换为01背包问题，也就是背包容量为k的时候，放入0不能超过m，放入1不能超过n，所获得的价值最大；
dp[k][m][n] = max(dp[k - 1][m][n], dp[k - 1][m - cnt[k][0]][n - cnt[k][1]] + 1)

3、代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for(int i = 0; i < len; i++){
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if(c == '0'){
                    zero++;
                }else {
                    one++;
                }
            }
            cnt[i] = new int[]{zero, one};
        }
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        for(int k = 1; k <= len; k++){
            int zero = cnt[k - 1][0], one = cnt[k - 1][1];
            for(int i = 0; i <= m; i++){
                for(int j = 0; j <= n; j++){
                    int a = dp[k - 1][i][j];
                    int b = (i >= zero && j >= one) ? dp[k - 1][i - zero][j - one] + 1 : 0;
                    dp[k][i][j] = Math.max(a, b);
                }
            }
        }

        return dp[len][m][n];
    }
}