Today's Challenge

https://leetcode.com/problems/ones-and-zeroes/

Ones and Zeroes - LeetCode

@cache를 쓰는 코드는 처음 봄. 메모이제이션에 사용될 수 있구먼..
처음엔 단순히 0과 1을 세서 m, n보다 작으면 출력하는 문제인 줄 알았는데, 그냥 DP 였음.

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        counter = [[s.count("0"), s.count("1")] for s in strs]
        
        @cache
        def dp(i, j, idx):
            if i < 0 or j < 0:
                return -math.inf
            if idx == len(strs):
                return 0
            return max(dp(i, j, idx+1), 1 + dp(i-counter[idx][0], j-counter[idx][1], idx+1))
        return dp(m, n, 0)