474.一和零

发表于： 分类于：
字数： 600 阅读：≈ 2分钟

1️⃣474.一和零

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

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

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

思路

基本思想

每次选择集合中的元素时，选择0和1尽量少的元素。

背包的容量是m，n二维，放进一个字符串，背包的容量变成m-zeroNum，n-oneNum，所以需要统计每一个字符串的0,1数量，判断当前字符串加入到背包中价值是否更大

递推方程为： $$ dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1) $$ 判断当前字符串是否加入背包中，背包初始化全为0

执行流程

dp[i][j]代表可以放i个0，j个1时背包最多可以装下多少个字符串元素

  1. 初始化背包，二维dp数组全为0
  2. 对于每一个字符串，统计出现的0,1数量
  3. 应用递推方程判断当前字符串是否加入
  4. 返回dp[m][n]作为最终结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //初始化dp数组全为0
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(auto s:strs){
            int zeroNum=0;
            int oneNum=0;
            for(auto c:s){//统计字符串出现的0，1个数
                if(c=='0')
                    ++zeroNum;
                else
                    ++oneNum;
            }
            //对于每一个字符串，更新dp数组
            for(int i=m;i>=zeroNum;--i){//从后向前减小背包容量
                for(int j=n;j>=oneNum;--j){
                    dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
};

总结

主要是知道如何将问题转化为背包问题，知道m，n共同组成了背包的容量，然后应用背包问题的流程解决当前问题

当前物品依次加入背包中，对于当前物品来说，背包的容量逐渐减小，分别对应外层和内层循环