LC-2209 Hard LeetCode

2209. Minimum White Tiles After Covering With Carpets

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 37% Topics: String, Dynamic Programming, Prefix Sum

Reading material

Strings 12 min 1-D Dynamic Programming 16 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(m * n)

# dp
class Solution(object):
    def minimumWhiteTiles(self, floor, numCarpets, carpetLen):
        """
        :type floor: str
        :type numCarpets: int
        :type carpetLen: int
        :rtype: int
        """
        dp = [[0]*(numCarpets+1) for _ in xrange(len(floor)+1)]  # dp[i][j] : min number of white tiles in the first i floors with j carpets
        for i in xrange(1, len(dp)):
            dp[i][0] = dp[i-1][0] + int(floor[i-1])
            for j in xrange(1, numCarpets+1):
                dp[i][j] = min(dp[i-1][j] + int(floor[i-1]), dp[max(i-carpetLen, 0)][j-1])
        return dp[-1][-1]

Solution from kamyu104/LeetCode-Solutions · MIT