474. 一和零

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/ones-and-zeroes/
Star
给你一个二进制字符串数组 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
通过次数81,204提交次数132,035

法1 动态规划 三位dp

思路
本题因为每个物品有两个属性，所以需要三维dp
状态定义 dp[i][j][k]: dp[i][j][k]前k个字符串中，最多有 m个0和 n个1的最大子集中元素的个数。 即 j 和k 共同为背包容量，需要同时满足才能装进去
状态转移：
  • 不考虑当前字符串 dp[i][j][k] = dp[i-1][j][k]
  • 考虑当前字符串, dp[i][j][k] = dp[i-1][j-zeros][k-ones] + 1
题解
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # dp[i][j][k]前k个字符串中，最多有 m个0和 n个1的最大子集中元素的个数
        dp = [[[0]*(n+1) for _ in range(m+1)] for _ in range(len(strs)+1)]
        
        for i in range(1, len(strs)+1):
            # 计算当前字符串中 0 1 的个数
            str_ = strs[i-1]
            ones, zeros = 0, 0
            for char in str_:
                if char == "0":
                    zeros += 1
                else:
                    ones += 1

            for j in range(0, m+1):
                for k in range(0, n+1):
                    # 不考虑当前字符
                    dp[i][j][k] = dp[i-1][j][k]
                    # 考虑当前字符，
                    # 一个字符串为一个整体，所以m和n同时判断，
                    # 只有同时满足才可以装进去
                    if j - zeros >= 0 and k - ones >= 0:
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-zeros][k-ones]+1)

        return dp[-1][-1][-1]

法2 动态规划 二维dp

思路
本题应该是三维DP的，这里做了状态压缩。
dp[i][j] : 剩余空间为 i,j 的时候，最多可以装多少。那么，只要剩余空间比当前物品需要的空间大，都可以选择。
题解
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # dp[i][j] : 剩余空间为 i,j 的时候，最多可以装多少
        dp = [[0] * (m+1) for _ in range(n+1)]

        for s in strs:
            # 获取当前字符串的0 和 1 的个数
            ones, zeros = 0, 0
            for char in s:
                if char == "0":
                    zeros += 1
                else:
                    ones += 1
            # 只要比该物品大，都可以选择该物品
            for i in range(n, ones-1, -1):
                for j in range(m, zeros-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-ones][j-zeros]+1)

        return dp[n][m]