0474. 一和零 #

标签：数组、字符串、动态规划
难度：中等

题目大意 #

给定一个二进制字符串数组 strs，以及两个整数 m 和 n。

要求：找出并返回 strs 的最大子集大小，该子集中最多有 m 个 0 和 n 个 1。

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

解题思路 #

可以转换为 0-1 背包问题来做。

把 0 的个数和 1 的个数视作一个二维背包的容量。每一个字符串都当做是一件物品，其成本为字符串中 1 的数量和 0 的数量，每个字符串的价值为 1。

则可以定义状态 dp[i][j] 为：最多有 i 个 0 和 j 个 1 的字符串 strs 的最大子集的大小为 dp[i][j]。

则递推公式为：dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)。

意思为：填满由 i 个 0 和 j 个 1 构成的二维背包的最多物品数为下面两种情况中的最大值：

使用之前字符串填满容量为 i - zero_num、j - one_num 的背包的物品数 + 当前字符串价值
选择之前字符串填满容量为 i、j 的物品数。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        
        for str in strs:
            one_num = 0
            zero_num = 0
            for ch in str:
                if ch == '0':
                    zero_num += 1
                else:
                    one_num += 1
            for i in range(m, zero_num - 1, -1):
                for j in range(n, one_num - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)

        return dp[m][n]