题目

题目来源：力扣（LeetCode）

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

思路分析

动态规划

这道题可以转化成背包问题进行求解。经典的背包问题可以使用二维动态规划求解，两个维度分别是 物品 和 容量。这道题有两种容量，因此需要使用三维动态规划求解，三个维度分别是字符串、0的容量和 1的容量。

1、状态定义
定义三维数组 dp，其中 dp[i][j][k] 表示在前 i 个字符串中，使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量。

2、确定递推公式
当 1 ≤ i ≤ l 时，对于 strs 中的第 i 个字符串（计数从 1 开始），首先遍历该字符串得到其中的 0 和 1 的数量，分别记为 zeros 和 ones，然后对于 0 ≤ j ≤m 和 0 ≤ k ≤ n，计算 dp[i][j][k] 的值。

当 0 和 1 的容量分别是 j 和 k 时，考虑以下两种情况：

  • 如果 j < zeros 或 k < ones，即当前字符串中 0 或 1 的数量比 0 和 1 的容量还要大，那么当前第 i 个字符串是不能选的，因此有 dp[i][j][k] = dp[i - 1][j][k]

  • 如果 j ≥ zeros 且 k ≥ ones，即当前字符串中 0 和 1 的数量比 0 和 1 的容量小，那么当前第 i 个字符串可以选择，也可以不选择：

    • 如果选择，则有：dp[i][j][k]=dp[i - 1][j - zeros][k - ones] + 1 (这里加 1 就表示选择了当前第 i 个字符)

    • 如果不选择，则有：dp[i][j][k]=dp[i−1][j][k]

dp[i][j][k] 的值应取两者中的最大值：max(dp[i−1][j][k], dp[i - 1][j - zeros][k - ones] + 1)

因此状态转移方程为：

dp[i][j][k] = dp[i - 1][j][k] (j<zeros ∣ k<ones)

dp[i][j][k] = max(dp[i−1][j][k], dp[i - 1][j - zeros][k - ones] + 1) (j ≥ zeros & k ≥ ones)

在算法实现时我们只考虑 j ≥ zeros & k ≥ ones 的情况，因此最终的状态转移方程为：
dp[i][j][k] = max(dp[i−1][j][k], dp[i - 1][j - zeros][k - ones] + 1)

3、状态初始化
当没有任何字符串可以使用时，可以得到的字符串数量只能是 0，因此动态规划的边界条件是：当 i = 0 时，对任意 0 ≤ j ≤ m 和 0 ≤ k ≤ n，都有 dp[i][j][k] = 0 。

4、遍历顺序
01背包问题外层for循环遍历物品，内层for循环遍历背包容量，
那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n

5、输出值
最后我们输出的是最后一个状态，假设数组str的长度为 len，则最终答案为dp[len][m][n] 。

代码实现

  1. /**
  2.  * @param {string[]} strs
  3.  * @param {number} m
  4.  * @param {number} n
  5.  * @return {number}
  6.  */
  7. var findMaxForm = function (strs, m, n) {
  8.   const length = strs.length;
  9.   // 定义三维数组
  10.   // 其中 dp[i][j][k] 表示在前 i 个字符串中，使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量
  11.   const dp = new Array(length + 1).fill(0).map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)));
  12.   // 01背包 外层for循环遍历物品
  13.   // 在这里 物品 就是 strs 里的字符串
  14.   for (let i = 1; i <= length; i++) {
  15.     // 统计当前字符串中 0 和 1 的数量
  16.     const zerosOnes = getZerosOnes(strs[i - 1]);
  17.     let zeros = zerosOnes[0], ones = zerosOnes[1];
  18.     // 01背包 内层循环遍历背包容量
  19.     // 在这里 背包容量就是题目描述中的m和n
  20.     for (let j = 0; j <= m; j++) {
  21.       for (let k = 0; k <= n; k++) {
  22.         dp[i][j][k] = dp[i - 1][j][k];
  23.         // j ≥ zeros 且 k ≥ ones，即当前字符串中 0 和 1 的数量比 0 和 1 的容量小，
  24.         // 那么当前第 i 个字符串可以选择，也可以不选择，取两者的最大值
  25.         if (j >= zeros && k >= ones) {
  26.           dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1);
  27.         }
  28.       }
  29.     }
  30.   }
  31.   // 最终得到 dp[length][m][n] 的值即为答案。
  32.   return dp[length][m][n];
  33. };
  35. // 统计 0 和 1 的数量
  36. const getZerosOnes = (str) => {
  37.   const zerosOnes = new Array(2).fill(0);
  38.   const length = str.length;
  39.   for (let i = 0; i < length; i++) {
  40.     zerosOnes[str[i].charCodeAt() - '0'.charCodeAt()]++;
  41.   }
  42.   return zerosOnes;
  44. }

空间优化

由于 dp[i][][] 的每个元素值的计算只和 dp[i - 1][][] 的元素值有关，因此可以使用滚动数组的方式，去掉 dp 的第一个维度，将空间复杂度优化到 O(mn)。

实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是 dp[i - 1][][] 中的元素值。

  1. /**
  2.  * @param {string[]} strs
  3.  * @param {number} m
  4.  * @param {number} n
  5.  * @return {number}
  6.  */
  7. var findMaxForm = function (strs, m, n) {
  8.   // 定义二维数组
  9.   // dp[i][j] 表示在前 i 个字符串中，使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量
  10.   const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  11.   const length = strs.length;
  12.   // 01背包 外层for循环遍历物品
  13.   // 在这里 物品 就是 strs 里的字符串
  14.   for (let i = 0; i < length; i++) {
  15.     // 统计当前字符串中 0 和 1 的数量
  16.     const zerosOnes = getZerosOnes(strs[i]);
  17.     const zeros = zerosOnes[0], ones = zerosOnes[1];
  18.     // 01背包 内层循环遍历背包容量且从后向前遍历
  19.     // 在这里 背包容量就是题目描述中的m和n
  20.     for (let j = m; j >= zeros; j--) {
  21.       for (let k = n; k >= ones; k--) {
  22.         dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
  23.       }
  24.     }
  25.   }
  26.   return dp[m][n];
  27. };
  29. // 统计 0 和 1 的数量
  30. const getZerosOnes = (str) => {
  31.   const zerosOnes = new Array(2).fill(0);
  32.   const length = str.length;
  33.   for (let i = 0; i < length; i++) {
  34.     zerosOnes[str[i].charCodeAt() - '0'.charCodeAt()]++;
  35.   }
  36.   return zerosOnes;
  37. }

参考阅读 https://leetcode-cn.com/problems/ones-and-zeroes/solution/yi-he-ling-by-leetcode-solution-u2z2/ https://leetcode-cn.com/problems/ones-and-zeroes/solution/474-yi-he-ling-01bei-bao-xiang-jie-by-ca-s9vr/ https://leetcode-cn.com/problems/ones-and-zeroes/solution/gong-shui-san-xie-xiang-jie-ru-he-zhuan-174wv/