【Leetcode Daily】474一和零

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个字符串数组，其中的字符串均由 0 和 1 组成，同时给两个数字，m n，要求找出一个字符串子集，使得该子集内的字符串个数尽可能大的同时，0 和 1 的数量分别不超过 m 和 n。

思路分享

• 我居然能自己看出来这个是 01背包 问题了，确实进步啦，这种问题采用 选或不选 的思路就行。

  https://leetcode.cn/problems/ones-and-zeroes/solutions/3038333/yi-bu-bu-si-kao-cong-ji-yi-hua-sou-suo-d-lqio/?envType=daily-question&envId=2025-11-11

• 但我觉着需要注意的难点在于记忆化搜索转换成递推的形式，在于考虑边界和初始化，毕竟记忆化搜索只要 return 就行了，而递推要考虑的就多了。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 空间优化
        l = len(strs)
        f = [[0]*(n+1) for _ in range(m+1)]
        for i, s in enumerate(strs):
            z = s.count('0')
            o = len(s) - z
            for j in range(m, -1, -1):
                for k in range(n, -1, -1):
                    if z <= j and o <= k:
                        f[j][k] = max(f[j-z][k-o]+1, f[j][k])
                    else:
                        f[j][k] = f[j][k]
        return f[m][n]

        # 递推
        # l = len(strs)
        # f = [[[0]*(n+1) for _ in range(m+1)] for _ in range(l+1)]
        # for i, s in enumerate(strs):
        #     z = s.count('0')
        #     o = len(s) - z
        #     for j in range(m+1):
        #         for k in range(n+1):
        #             if z <= j and o <= k:
        #                 f[i+1][j][k] = max(f[i][j-z][k-o]+1, f[i][j][k])
        #             else:
        #                 f[i+1][j][k] = f[i][j][k]
        # return f[-1][m][n]

        # 记忆化搜索
        # @cache
        # def dfs(i:int, zero:int, one:int) -> int:
        #     if i < 0:
        #         return 0
        #     z = strs[i].count('0')
        #     o = len(strs[i]) - z
        #     if z <= zero and o <= one:
        #         return max(dfs(i-1, zero-z, one-o)+1, dfs(i-1, zero, one))
        #     return dfs(i-1, zero, one)
        # return dfs(len(strs)-1, m, n)