Cocolib

Appearance

On this page

一和零 ​

TIP

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

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

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

image-20230625091045738

思路 ​

动规五部曲 ​

  1. 确定dp数组以及下标的含义：dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
  2. 确定递推公式：dp[i][j] = dp[i-str[i].0的个数][j-str[i].1的个数]+1
  3. dp数组如何初始化：dp[0][0] = 0
  4. 确定遍历顺序
  5. 举例推导dp数组
js
var findMaxForm = function(strs, m, n) {
    let dp = new Array(m+1).fill(0).map(v => new Array(n+1).fill(0))
    let x = 0
    let y = 0
    for(let s in strs){             //物品
        x = 0
        y = 0
        for(let c in strs[s]){      //统计0、1个数
            if(strs[s][c]==='0') x++  
            else y++  
        }
        for(let i=m;i>=x;i--){      //背包
            for(let j=n;j>=y;j--){
                dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1)
            }
        }
    }
    return dp[m][n]
};