↓Skip to main content
  1. Posts/

LeetCode-474 一和零

·1 min·
Table of Contents

LeetCode-474 一和零 #

Solution 1 #

有两个容量约束的背包问题.

代码如下:

class Solution:
    def findMaxForm(self, strs: list[str], m: int, n: int) -> int:
        strs = [(sum([ch == '0' for ch in s]), sum([ch == '1' for ch in s])) for s in strs]
        strs = sorted(strs)
        
        @cache
        def f(m, n, k): 
            if k < 0 or m < 0 or n < 0 or (m == 0 and n == 0):
                return 0
            res = f(m, n, k -1)
            x, y = strs[k]
            if m >= x and n >= y:
                res = max(res, f(m-x, n-y, k-1) + 1)
            return res
    
        return f(m, n, len(strs) - 1)