LeetCode 474题 “Ones and Zeroes” 是一个经典的动态规划问题。题目要求我们在给定的字符串数组中，选择尽可能多的字符串，同时满足这些字符串中 ‘0’ 和 ‘1’ 的数量分别不超过给定的两个限制值。

题目描述

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

请你找出并返回 strs 的最大子集的大小，该子集中最多包含 m 个 ‘0’ 和 n 个 ‘1’。

示例

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 4 个字符串可以选择。 可以选择 "10"、"0001"、"1" 和 "0"。

解题思路

我们可以使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示最多包含 i 个 ‘0’ 和 j 个 ‘1’ 的最大子集大小。

1. 初始化：dp[0][0] = 0，因为不包含任何字符串时，’0′ 和 ‘1’ 的数量都是 0。
2. 遍历字符串数组：对于每个字符串，统计其中的 ‘0’ 和 ‘1’ 的数量。
3. 更新 dp 数组：从后向前更新 dp 数组，以避免重复使用同一个字符串。

代码实现

def findMaxForm(strs, m, n):

dp = [[0] * (n + 1) for _ in range(m + 1)]

# 遍历每个字符串
for s in strs:
    zeros = s.count('0')
    ones = s.count('1')

    # 从后向前更新 dp 数组
    for i in range(m, zeros - 1, -1):
        for j in range(n, ones - 1, -1):
            dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

return dp[m][n]

print(findMaxForm(strs, m, n)) # 输出：4

解释

1. 初始化 dp 数组：创建一个 (m+1) x (n+1) 的二维数组，初始值都为 0。
2. 统计每个字符串的 ‘0’ 和 ‘1’ 数量：使用 s.count('0') 和 s.count('1')。
3. 更新 dp 数组：从后向前更新是为了确保每个字符串只被使用一次。dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1) 表示在当前条件下，选择或不选择当前字符串的最大子集大小。

复杂度分析

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

通过这种方法，我们可以有效地解决 “Ones and Zeroes” 问题，找到满足条件的最大子集大小。