474. 一和零

01背包

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {

        /**
         * 这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品
         * dp[i][j]定义为最多有i个0和j个1的strs的最大子集的大小
         */
        int[][] dp = new int[m + 1][n + 1];

        /**
         * 计算每个字符串中0和1的个数
         */
        for (String str : strs) {

            int zero = 0;
            int one = 0;

            for (char c : str.toCharArray()) {

                if (c == '0') {
                    zero++;
                } else {
                    one++;
                }
            }

            /**
             * 遍历背包容量从后往前
             */
            for (int i = m; i >= zero; i--) {

                for (int j = n; j >= one; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
                }
            }
        }

        return dp[m][n];
    }
}

/**
 * 时间复杂度 O(m*n*length)
 * 空间复杂度 O(m*n)
 */

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