DP + edge case optimization with explanations
Two edge cases can be handled explicitly before running DP:\n(1) if numCarpets * carpetLen >= n, i.e. the totally length of carpets altogether is longer than th
Two edge cases can be handled explicitly before running DP:\n(1) `if numCarpets * carpetLen >= n`, i.e. the totally length of carpets altogether is longer than the length of `floor`, return 0 immediately;\n(2) `if carpetLen == 1`, then the problem becomes trivial and we can cover the carpets "greedily". Adding this edge check is particularly useful for a few long test cases (as it would save half of the time for such cases), which does help to get AC for this problem.\nThe rest of the code deals with the general cases by using DP, where `dp[i][j]` represents the minimum white tiles after covering with `j` carpets for first `i` tiles.\nPlease upvote if you find this solution helpful.\n```\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n        n = len(floor)\n\t\t# edge case handling\n        if numCarpets * carpetLen >= n:\n            return 0\n        if carpetLen == 1:\n            return max(sum([int(c) for c in floor]) - numCarpets, 0)\n\t\t# DP initialization\n        dp = [[None] * (numCarpets + 1) for _ in range(n + 1)]\n        for j in range(numCarpets + 1):\n            dp[0][j] = 0\n        for i in range(1, n + 1):\n            dp[i][0] = dp[i - 1][0] + int(floor[i - 1])\n\t\t# DP transition formula\n        for i in range(1, n + 1):\n            for j in range(1, numCarpets + 1):\n                dp[i][j] = min(dp[i - 1][j] + int(floor[i - 1]), dp[max(i - carpetLen, 0)][j - 1])\n        return dp[n][numCarpets]\n```
['Dynamic Programming', 'Python', 'Python3']