474. Ones and Zeroes

474. Ones and Zeroes

 

https://youtu.be/miZ3qV04b1g?si=ieg8qGyjhzei0dQq

 

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # memoization

        dp = {}  # 메모이제이션을 위한 딕셔너리 생성, 키는 (i, m, n), 값은 최대 부분집합 크기

        def dfs(i, m, n):
            if i == len(strs):  # 문자열 리스트를 모두 탐색했을 경우
                return 0  # 부분집합을 더 이상 추가할 수 없으므로 0 반환

            if (i, m, n) in dp:  # 이미 계산한 (i, m, n) 상태가 dp에 저장되어 있다면
                return dp[(i, m, n)]  # 저장된 값을 바로 반환하여 중복 계산 방지

            mCnt, nCnt = strs[i].count("0"), strs[i].count("1")  # 현재 문자열에서 '0'과 '1'의 개수를 계산
            dp[(i, m, n)] = dfs(i + 1, m, n)  # 현재 문자열을 포함하지 않고 다음 문자열로 넘어간 경우의 결과를 저장

            if mCnt <= m and nCnt <= n:  # 현재 문자열을 포함할 수 있는지 확인 (남은 '0'과 '1' 개수 조건 만족)
                # 포함하지 않은 경우와 포함한 경우 중 더 큰 값을 저장
                dp[(i, m, n)] = max(dp[(i, m, n)], 1 + dfs(i + 1, m - mCnt, n - nCnt))
            return dp[(i, m, n)]  # 현재 상태 (i, m, n)에 대한 결과 반환

        return dfs(0, m, n)  # 초기 상태에서 dfs 시작 (i=0, m=m, n=n)

 

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # DP

        dp = defaultdict(int)

        for i in range(len(strs)):
            s = strs[i]
            mCnt, nCnt = s.count("0"), s.count("1")

            for m_i in range(0, m+1):
                for n_i in range(0, n+1):
                    if mCnt <= m_i and nCnt <= n_i:
                        dp[(i, m_i, n_i)] = max(dp[(i-1, m_i, n_i)], 1 + dp[(i-1, m_i-mCnt, n_i-nCnt)])
                    else:
                        dp[(i, m_i, n_i)] = dp[(i-1, m_i, n_i)]
            
        return dp[(len(strs)-1, m, n)]

 

=> 코드 최적화

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # DP
        dp = defaultdict(int)

        for s in strs:
            mCnt, nCnt = s.count("0"), s.count("1")

            for m_i in range(m, mCnt-1, -1):
                for n_i in range(n, nCnt-1, -1):
                    dp[(m_i, n_i)] = max(dp[(m_i, n_i)], 1 + dp[(m_i-mCnt, n_i-nCnt)])
            
        return dp[(m, n)]