474.一和零

红太狼 2023-10-16 16:41 34阅读 0赞

#### 474.一和零 ####

*  题干描述
 *  解题思路
 *   *  1. 确定dp数组（dp table）以及下标的含义
     *  2. 确定递推公式
     *  3. dp数组如何初始化
     *  4. 确定遍历顺序
     *  5. 举例推导dp数组
 *  总结
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

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

## 解题思路 ##

本题不少同学会认为是多重背包，一些题解也是这么写的。

其实本题并不是多重背包，再来看一下这个图，捋清几种背包的关系。

![在这里插入图片描述][3e66fedcd0424abc9dbd54bba496cccb.png]  
多重背包是每个物品，数量不同的情况。

**本题中strs数组里的元素就是物品，每个物品都是一个！**

**而m 和 n相当于是一个背包，两个维度的背包。**

理解成多重背包的同学主要是把m和n混淆为物品了，感觉这是不同数量的物品，所以以为是多重背包。

但本题其实是01背包问题！

只不过这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。

开始动规五部曲。

### 1. 确定dp数组（dp table）以及下标的含义 ###

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

### 2. 确定递推公式 ###

dp\[i\]\[j\] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp\[i\]\[j\] 就可以是 dp\[i - zeroNum\]\[j - oneNum\] + 1。

然后我们在遍历的过程中，取dp\[i\]\[j\]的最大值。

所以递推公式：dp\[i\]\[j\] = max(dp\[i\]\[j\], dp\[i - zeroNum\]\[j - oneNum\] + 1);

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

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

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

### 3. dp数组如何初始化 ###

在\*\*动态规划：关于01背包问题，你该了解这些！（滚动数组）\*\*中已经讲解了，01背包的dp数组初始化为0就可以。

因为物品价值不会是负数，初始为0，保证递推的时候dp\[i\]\[j\]不会被初始值覆盖。

### 4. 确定遍历顺序 ###

在\*\*动态规划：关于01背包问题，你该了解这些！（滚动数组）\*\*中，我们讲到了01背包为什么一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n。

代码如下：

for(string 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);
    		}
    	}
    }

有同学可能想，那个遍历背包容量的两层for循环先后循序有没有什么讲究？

没讲究，都是物品重量的一个维度，先遍历哪个都行！

### 5. 举例推导dp数组 ###

以输入：\[“10”,“0001”,“111001”,“1”,“0”\]，m = 3，n = 3为例

最后dp数组的状态如下所示：  
![在这里插入图片描述][65e98d074f924394a8d71e5042f7a3f9.png]

## 总结 ##

不少同学刷过这道题，可能没有总结这究竟是什么背包。

此时我们讲解了0-1背包的多种应用，

*  **纯 0 - 1 背包**是求 给定背包容量 装满背包 的最大价值是多少。
 *  **416. 分割等和子集** 是求 给定背包容量，能不能装满这个背包。
 *  **1049. 最后一块石头的重量 II** 是求 给定背包容量，尽可能装，最多能装多少。
 *  **494. 目标和**是求 给定背包容量，装满背包有多少种方法。
 *  本题是求 给定背包容量，装满背包最多有多少个物品。

所以在代码随想录中所列举的题目，都是 0-1背包不同维度上的应用，大家可以细心体会！

## 代码实现 ##

class Solution {
        
        // 474.一和零
        public int findMaxForm(String[] strs, int m, int n){
        
            // dp[i][j]表示i个0和j个1时的最大子集
            int[][] dp = new int[m + 1][n + 1];
            int oneNum, zeroNum;
            for(String str : strs){
        
                oneNum = 0;
                zeroNum = 0;
                for(char ch : str.toCharArray()){
        
                    if(ch == '0'){
        
                        zeroNum++;
                    } else{
        
                        oneNum++;
                    }
                }
                // 倒序遍历
                for(int i = m; i >= zeroNum; i--){
        
                    for(int j = n; j >= oneNum; j--){
        
                        dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    }

**参考资料**：[代码随想录-474.一和零][-474.]

[Link 1]: https://leetcode.cn/problems/ones-and-zeroes/
[3e66fedcd0424abc9dbd54bba496cccb.png]: https://img-blog.csdnimg.cn/3e66fedcd0424abc9dbd54bba496cccb.png
[65e98d074f924394a8d71e5042f7a3f9.png]: https://img-blog.csdnimg.cn/65e98d074f924394a8d71e5042f7a3f9.png
[-474.]: https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE