[Python3] DP solution in O(MN) time and O(N) space
dp solution:\n dp[i][j] represents for the max number of covered white tiles within floor[:j + 1] using i carpets\n dp[i][j] = max(max(dp[i][k] for k in range(j
# dp solution:\n* `dp[i][j]` represents for the max number of covered white tiles within `floor[:j + 1]` using `i` carpets\n* `dp[i][j] = max(max(dp[i][k] for k in range(j)), white count in floor[j - carpetLen : j + 1] + dp[i - 1][j - carpetLen])`\n```\ndef minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n    # dp\n    n = len(floor)\n    cnt_white = []\n    cnt = 0\n    for i in floor:\n        cnt += int(i)\n        cnt_white.append(cnt)\n\t\t\n    dp = [[0] * (n) for _ in range(numCarpets + 1)]\n    for i in range(1, numCarpets + 1):\n        max_ = 0\n        for j in range(n):\n            # i carpets\n            # cover [0:j + 1] floor\n            if j - carpetLen < 0:\n                dp[i][j] = cnt_white[j]\n            else:\n                dp[i][j] = max(max_, cnt_white[j] - cnt_white[j - carpetLen] + dp[i - 1][j - carpetLen])\n                max_ = dp[i][j]\n    return cnt - dp[-1][-1]\n```\n\n# optimization:\nsince `dp[i]` only depend on `dp[i-1]`, we cound reduce space complexity to `O(N)`\n```\ndef minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n    # dp\n\tn = len(floor)\n    cnt_white = []\n    cnt = 0\n    for i in floor:\n        cnt += int(i)\n        cnt_white.append(cnt)\n    dp = [0] * (n)\n    for i in range(1, numCarpets + 1):\n        nxt = []\n        max_ = 0\n        for j in range(n):\n            if j - carpetLen < 0:\n                nxt.append(cnt_white[j])\n            else:\n                nxt.append(max(max_, cnt_white[j] - cnt_white[j - carpetLen] + dp[j - carpetLen]))\n                max_ = nxt[-1]\n        dp = nxt\n    return cnt - dp[-1]\n```
['Dynamic Programming', 'Python']