LeetCode-474. 一和零

╰半橙微兮° 2024-03-25 14:00 79阅读 0赞

#### 目录 ####

*   *  题目思路
     *  动态规划
     *  动态规划(压缩)

题目来源  
[474. 一和零][474.]

### 题目思路 ###

为了方便理解, 先把两个变量删掉一个, 那么题目变为: 返回最大子集的长度,该子集中最多有m个0  
此时的解题思路就是正常的二维dp:

1.创建一个dp\[len+1\]\[m+1\], 其中len = strs.length.  
2.dp\[i\]\[j\] 代表: 在\[0-i\]个字符串中, 0有i个时最多有几个子串.  
3.那么递推公式:

> if( i-zeros>=0) : dp\[i\]\[j\] = Math.max(dp\[i\]\[j\], dp\[i-1\]\[i-zeros\] + 1); else : dp\[i\]\[j\] = dp\[i-1\]\[j\];  
> 其中zeros=该字符串中0的数量.  
> 解释一下这里为什么是dp\[i-1\]\[j-zeros\] + 1, 因为如果要把当前第i个字符串算入子串的话, 需要zeros的容量, 所以前i-1的子串最多只能占i-zeros的容量.

理解了上面所说的一个变量的情况, 那么两个变量的情况就简单了, 就是在dp\[len+1\]\[m+1\]后再加一个维度变成dp\[len+1\]\[m+1\]\[n+1\].

此时dp\[i\]\[j\]\[k\] 代表: 在\[0-i\]个字符串中, 0有j个, 1有k个时最多有几个子串.  
递推公式变成:

> if( j-zeros >= 0 && k-ones>=0) : dp\[i\]\[j\]\[k\] = Math.max(dp\[i-1\]\[j\]\[k\], dp\[i-1\]\[j-zeros\]\[k-ones\] + 1); else: dp\[i\]\[j\]\[k\] = dp\[i-1\]\[j\]\[k\];  
> 其中zeros=该字符串中0的数量. ones代表该字符串中1的数量.  
> 解释一下这里为什么是dp\[i-1\]\[j-zeros\]\[k-ones\] + 1, 因为如果要把当前第l个字符串算入子串的话, 需要zeros和ones的容量, 所以前i-1的子串最多只能占\[j-zeros\] && \[k-ones\]的容量.

### 动态规划 ###

class Solution {
        
        public int findMaxForm(String[] strs, int m, int n) {
        
            if(strs == null){
        
                return 0;
            }
            int[][][] dp = new int[strs.length+1][m+1][n+1];
            for(int i=1;i<=strs.length;i++){
        
                int zero = 0;
                int one = 0;
                String str = strs[i-1];
                for (int x = 0; x < str.length(); x++){
        
                    if (str.charAt(x) == '0')
                        zero++;
                    else
                        one++;
                }
                for(int j = 0;j<=m;j++){
        
                    for(int k=0;k<=n;k++){
        
                        if(j>=zero && k>=one){
        
                            dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zero][k-one]+1);
                        }else{
        
                            dp[i][j][k] = dp[i-1][j][k];
                        }
                    }
                }
            }
            return dp[strs.length][m][n];
        }
    }

![在这里插入图片描述][24b0e9c476d64198954f26ab015c8dfa.png]

### 动态规划(压缩) ###

*  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数组如何初始化

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

*  4.确定遍历顺序

外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！  
那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n。

for(String str :strs){
        
                int zero = 0;
                int one = 0;
                for (char ch : str.toCharArray()) {
        
                    if (ch == '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);
                    }
                }
            }

*  5.举例推导dp数组

以输入：\[“10”,“0001”,“111001”,“1”,“0”\]，m = 3，n = 3为例  
最后dp数组的状态如下所示：

![在这里插入图片描述][0a70104dd40147e7b48a68da3986140f.png]  
代码如下

class Solution {
        
        public int findMaxForm(String[] strs, int m, int n) {
        
            if(strs == null){
        
                return 0;
            }
            int[][] dp = new int[m+1][n+1];
            for(String str :strs){
        
                int zero = 0;
                int one = 0;
                for (char ch : str.toCharArray()) {
        
                    if (ch == '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];
        }
    }

![在这里插入图片描述][d059f885cee24c6ebc13e712ae5cfeb0.png]

[474.]: https://leetcode.cn/problems/ones-and-zeroes/
[24b0e9c476d64198954f26ab015c8dfa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/80515800b4794b298f8c500872189228.png
[0a70104dd40147e7b48a68da3986140f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/80aa749a0bb14299b4cdc42d3a4fd7ee.png
[d059f885cee24c6ebc13e712ae5cfeb0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a001bda418014f09b3ae51e4f3f29302.png