Shouyu

Appearance

一和零 ​

题目描述 ​

给你一个二进制字符串数组 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 。

题目链接：https://leetcode.cn/problems/ones-and-zeroes/

文章讲解：https://programmercarl.com/0474.一和零.html

思路 ​

这道题可以把这个子集映设为背包，而这个背包有两个维度的容量，来限制这个背包。这个背包的容量是 5 和 3 。物品是一个二进制字符串，也有两个维度的属性，分别是0的数量和1的数量。

求最大子集长度，也就是求这个背包所能够背的物品最大数量。

动规五部曲 ​

1、dp数组及下标含义 ​

dp[i][j] : 最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

2.、递推公式 ​

这里物品和两个个容量本身应该是三维的 DP 数组，我们只设置了容量这个二维 DP 数组。那么就要用类似滚动数组的方式处理物品/二进制字符串。就说里面有 考虑 [0,m ]的str ，

strs[m] 里面有zeroNum个0，oneNum个1。

情况1：strs[m]在这个子集中，那么 dp[i][j] 去掉最后一个str 就是 dp[i - zeroNum][j - oneNum]。就有dp[i][j] = dp[i - zeroNum][j - oneNum] + 1

情况2：strs[m]不在这个子集中，那么就是保持原值 dp[i][j]。这里注意千万不要想成dp[i-1][j]。之前的问题中，i-1 这个 i 是物品，而现在 i 和 j 都是容量。

取两者中的最大值。

回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

3、dp数组初始化 ​

01背包问题中 物品属性这里不会小于0，因此初始化为0即可。

4、确定遍历顺序 ​

外层便利字符串，内层遍历m和n，内层从后往前遍历

C++
for( auto str:strs){
    int oneNum = 0, zeroNum = 0;
    for (char c : str) {
        if (c == '0') zeroNum++;
        else oneNum++;
    }
    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);
        }
    }
}
5、举例推导 ​

以输入：["10","0001","111001","1","0"]，m = 3，n = 3为例，每处理完一个字符串后dp数组

C++
After processing string "10":
0 0 0 0 
0 1 1 1 
0 1 1 1 
0 1 1 1 
--------------------
After processing string "0001":
0 0 0 0 
0 1 1 1 
0 1 1 1 
0 1 1 1 
--------------------
After processing string "111001":
0 0 0 0 
0 1 1 1 
0 1 1 1 
0 1 1 1 
--------------------
After processing string "1":
0 1 1 1 
0 1 2 2 
0 1 2 2 
0 1 2 2 
--------------------
After processing string "0":
0 1 1 1 
1 2 2 2 
1 2 3 3 
1 2 3 3 
--------------------

代码实现 ​

C++
int findMaxForm(vector<string> &strs, int m, int n) {
    // dp[i][j] 定义为：当背包容量为 i 个 0 和 j 个 1
    // 时，最多能放入的字符串数量。 初始化为 0，表示在没有字符串或者背包容量为 0
    // 时，能放入的字符串数量为 0。
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    // 遍历每一个字符串，将其视为一个"物品"。
    for (string str : strs) {
        int zero_num = 0, one_num = 0;
        // 统计当前字符串中 0 和 1 的数量。
        for (char s : str) {
            if (s == '0')
                zero_num++;
            else
                one_num++;
        }
        // 动态规划的核心部分：从后往前遍历背包容量。
        // 这是为了避免重复使用同一个字符串（每个字符串只能用一次）。
        // 如果从前往后遍历，dp[i][j] 可能会在计算时重复加上当前字符串的价值。
        for (int i = m; i >= zero_num;
             i--) { // 遍历 0 的容量，从最大容量 m 开始递减。
            for (int j = n; j >= one_num;
                 j--) { // 遍历 1 的容量，从最大容量 n 开始递减。
                // dp[i][j] 的状态转移方程：
                // 1. 不选择当前字符串：dp[i][j]
                // 保持原值（即在考虑当前字符串之前的最大值）。
                // 2. 选择当前字符串：需要消耗 zero_num 个 0 和 one_num 个 1，
                //    此时背包剩余容量为 (i - zero_num, j - one_num)，
                //    再加上当前字符串的价值 1。
                // 取两者中的最大值。
                dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1);
            }
        }
    }
    // 最终 dp[m][n] 即为在最多 m 个 0 和 n 个 1
    // 的限制下，能组成的最大子集长度。
    return dp[m][n];
}