LeetCode 474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

思路：

采用动态规划，将本题转化为 01 背包问题。将字符串数组中的每一个字符串看作一个 物品，每个物品重量分为两个维度，0的个数为 x，1的个数为 y。因此想要将这个物品（字符串）放进背包（子集）中，就需要背包有足够的空间（m>=x，n>=y）来容纳它。dp[ i ][ j ] 表示容量为 i，j 的 背包 中所能装物品的最大个数。

递推公式：dp[ i ][ j ] = Math.max(dp[ i ][ j ]，dp[ i - x ][ j - y ] + 1 )。dp[ i ][ j ] 有两个来源，一是 物品（字符串）没有放进背包里面，那么 dp[ i ][ j ] 不变。二是 物品（字符串）放入了背包，则dp[ i ][ j ] = dp[ i - x ][ j - y ] + 1 ，背包的里面 0 和 1 的剩下的容量要减少，背包中装的物品的个数 +1。

初始化：dp[ 0 ][ 0 ] 显然为 0，其余的 dp 值也初始化为 0，避免初始值过大而覆盖 运算后的数据。遍历顺序：先遍历物品（字符串），再遍历背包容量。遍历背包容量时，要从大到小遍历，避免 将物品（字符串）重复添加。

代码：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m+1][n+1];
            for(String str:strs){
                int x=0,y=0;//x：0的数量 y：1的数量
                for(int k=0;k<str.length();k++){
                    if(str.charAt(k)=='0')x++;
                    else y++;
                }
                //i>=x,因为如果当前背包还能装下0的数量i小于当前str的0的数量x的话,
                //当前背包必然装不下当前str 
                for(int i=m;i>=x;i--){
                    for(int j=n;j>=y;j--){
                        dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1);
                    }
                }
            }
            return dp[m][n];
    }
}

参考：代码随想录