9. 一和零（474）

一、题目内容 中等

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

  二、解题思路

  本题中 strs 数组里的元素就是物品，每个物品都是一个！
  而 m 和 n 相当于是一个背包，两个维度的背包。

  这里两个维度的背包，并不是之前 01 背包理论文章中二维 dp 数组，依然是滚动数组，继续往下看就会明白。 只不过由于 m、n 是两个维度，所以需要用二维的 dp 数组来表示才可以。

:::warning 理解成多重背包的同学主要是把 m 和 n 混淆为物品了，感觉这是不同数量的物品，所以以为是多重背包。
但本题其实是01背包问题！ ::: 开始动规五部曲：

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

**dp[i][j]**：最多含有 i 个 0 和 j 个 1 的 strs 的最大子集的大小

1. 确定递推公式

首先strs[k]中有 zeroNum 个 0，oneNum 个 1，现在想知道 dp[i][j]是多少？
dp[i - zeroNum][j - oneNum]意味着找出之前能容纳i - zeroNum 个 0，j - oneNum 个 1
的子集，那么现在 dp[i][j]的大小就等于 dp[i - zeroNum][j - oneNum] + 1。

但是，每次遍历，可能dp[i][j] > dp[i - zeroNum][j - oneNum] + 1，我们要的是最大子集
所以递推公式应该是：**dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)**

1. dp 数组如何初始化

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

1. 确定遍历顺序

我们在 01 背包滚动数组讲到了为什么一定是外层 for 循环遍历物品，内层 for 循环遍历背包容量且从后向前遍历！
那么本题也是，物品就是 strs 里的字符串，背包容量就是题目描述中的 m 和 n。

// 遍历物品
for (let k = 0; k < strs.length; k++) {
  const str = strs[k]
  let zeroNum = 0, oneNum = 0
  for (const char of str) {
    if (char === '0') zeroNum += 1
    else oneNum += 1
  }
  // 遍历背包容量且从后向前遍历（滚动数组）
  for (let i = m; i >= zeroNum; i--) {
    for (let j = n; j >= oneNum; j--) {
      dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
    }
  }
}

1. 举例推导 dp 数组

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

三、具体代码

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))
  // 遍历物品
  for (let k = 0; k < strs.length; k++) {
    const str = strs[k]
    let zeroNum = 0, oneNum = 0
    for (const char of str) {
      if (char === '0') zeroNum += 1
      else oneNum += 1
    }
    // 遍历背包容量且从后向前遍历
    for (let i = m; i >= zeroNum; i--) {
      for (let j = n; j >= oneNum; j--) {
        dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
      }
    }
  }
  return dp[m][n]
};

四、其他解法