474. 一和零

🟠   🔖  数组 字符串 动态规划  🔗 力扣 LeetCode

题目

You are given an array of binary strings strs and two integers m and n.

Return _the size of the largest subset ofstrs such that there are at most _m **0 _' s and _n **1 ' s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3

Output: 4

Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.

Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.

{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1

Output: 2

Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints:

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

题目大意

给你一个二进制字符串数组 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 背包问题有一些相似之处。

可以定义一个三维动态规划数组 dp，其中 dp[i][j][k] 表示在前 i 个字符串中使用 j 个 '0' 和 k 个 '1' 的条件下，最大子集的长度。

动态规划的状态转移方程如下：

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

其中，zeros 表示第 i 个字符串中 '0' 的个数，ones 表示第 i 个字符串中 '1' 的个数。

接下来，遍历每个字符串，更新动态规划数组，最后返回 dp[len][m][n]，表示使用最多 m 个 '0' 和 n 个 '1' 条件下得到的最大字符串数目。

复杂度分析

• 时间复杂度：O(len * m * n)，其中 len 是字符串数组的长度。
• 空间复杂度：O(len * m * n)。

---

思路二：压缩状态的动态规划

注意到 dp[i][j][k] 都是通过上一行 dp[i-1][..][..] 转移过来的，再之前所有行的数据都不会再使用了。所以，我们可以对动态规划进行状态压缩，将三维 dp 数组压缩为二维，节约空间复杂度：

• dp[j][k] 表示在当前元素中，使用 j 个 '0' 和 k 个 '1' 的条件下，最大子集的长度；
• 遍历 strs 数组中的每个字符串 str，并更新 dp 数组。需要注意的是 j 和 k 应该从后往前反向遍历，确保了我们在更新当前状态时所依赖的状态已经被正确计算；
• 状态转移方程：dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1)；
• 最终结果存储在 dp[m][n] 中；

复杂度分析

• 时间复杂度：O(len * m * n)，其中 len 是字符串数组的长度。
• 空间复杂度：O(m * n)。

代码

动态规划

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
	const len = strs.length;
	const dp = new Array(len + 1)
		.fill(0)
		.map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)));

	for (let i = 1; i <= len; i++) {
		const zeros = [...strs[i - 1]].filter((i) => i == '0').length;
		const ones = strs[i - 1].length - zeros;
		for (let j = m; j >= 0; j--) {
			for (let k = n; k >= 0; k--) {
				if (zeros > j || ones > k) {
					dp[i][j][k] = dp[i - 1][j][k];
				} else {
					dp[i][j][k] = Math.max(
						dp[i - 1][j][k],
						dp[i - 1][j - zeros][k - ones] + 1
					);
				}
			}
		}
	}
	return dp[len][m][n];
};

压缩状态的动态规划

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
	const len = strs.length;
	const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
	for (let str of strs) {
		const zeros = [...str].filter((i) => i == '0').length;
		const ones = str.length - zeros;

		for (let j = m; j >= 0; j--) {
			for (let k = n; k >= 0; k--) {
				if (j >= zeros && k >= ones) {
					dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
				}
			}
		}
	}
	return dp[m][n];
};

相关题目

题号	标题	题解	标签	难度
600	不含连续1的非负整数		动态规划
2031	1 比 0 多的子数组个数 🔒		树状数组 线段树 数组 4+
2155	分组得分最高的所有下标		数组