Python 7-line DP O(kmn) time O(mn) space - 0/1 Backpack


  • 0
    class Solution(object):
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            dp = [[0] * (n + 1) for _ in range(0, m + 1)]
            for dj, dk in [(s.count("0"), s.count("1")) for s in strs]:
                for j in reversed(range(0, m + 1)):
                    for k in reversed(range(0, n + 1)):
                        if j - dj >= 0 and k - dk >= 0:
                            dp[j][k] = max(dp[j][k], dp[j - dj][k - dk] + 1)
            return dp[-1][-1]
    

    My original submission may be more readable.

    class Solution(object):
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            d = []
            for s in strs:
                d.append((s.count("0"), s.count("1")))
            dp = [[0] * (n + 1) for _ in range(0, m + 1)]
    
            for i in range(0, len(d)):
                for j in reversed(range(0, m + 1)):
                    for k in reversed(range(0, n + 1)):
                        dj, dk = d[i]
                        if j - dj >= 0 and k - dk >= 0:
                            dp[j][k] = max(dp[j][k], dp[j - dj][k - dk] + 1)
    
            return dp[-1][-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.