Python 3: FT 99%, TC O(N*C), SC O(N): 2D DP
Intuition\n\nUsually when the problem is on an array and we have a limited number of items, the solution is\n dynamic programming\n with two variables\n one is 
# Intuition\n\nUsually when the problem is on an array and we have a limited number of items, the solution is\n* dynamic programming\n* with two variables\n* one is the current index in the array\n* and the other is the number of items we\'ve used\n\nI found the DP relation to be a bit tricky, but after some wrangling, this is what I came up with.\n\nBased on the above insight we guess that we want `vis[i][k]` meaning\n* **fewest** visible white tiles\n* among tiles `0..i`\n* given that `k` carpets have been laid down\n\nFor `vis[i][k]`:\n* if we lay a carpet down ending at `i` there will be `vis[i-carpetLen][k-1]` tiles\n  * the carpet we lay down will cover `i-carpetLen+1..i`\n  * so the tiles visible are those with the `k-1` carpets up to tile `i-carpetLen`, the last not under the new carpet\n* **if we don\'t lay a carpet down at `i`, the `kth` carpet is earlier**\n  * to avoid an `O(N)` search we make `vis` the *fewest* visible up to i`, the cumulative min\n  * so the min visible with `k` carpets up to `i` is\n    * place `k` carpets among `0..i-1` and get the best answer: `vis[i-1][k]`\n    * and if the current tile is white then it\'s visible: `int(floor[i])`\n\nThis is good enough to avoid TLE and MLE.\n\n# Approach\n\nThe actual approach is more optimal to two respects.\n\n**Reduced memory: prior row trick.** The DP relation for `vis` only dpeends on `k-1`. Therefore we only need two rows:\n* the current row, `vis[:][k]`\n* the prior row: `vis[:][k-1]`\n\nThis saves on memory.\n\nMorever we can use the **swap trick.** Instead of allocating a new `curr` row every time, since we solve for all indices, at the end of each iteration, swap `curr` and `prev`. This is because the next iteration\'s `prev` is the current `curr`, and the current `prev` will not be used. So we can swap and overwrite the otherwise-useless `prev` in the next iteration. Not a big deal, but on platforms with refcounting and GC like Python and Java it can make a difference.\n\n(it can also make a difference even in C++, etc. because `malloc` and `free` are not free - have to coalesce free memory, find a suitable range, etc.)\n\n**Reduced time: end-to-end insight: If we lay `k` carpets end to end that covers the first `k*carpetLen` tiles. Therefore we know that `vis[0:k*carpetLen][k] == 0`.** And thus\n* we can set `vis[k*carpetLen-1][k] = 0` at the top of the loop\n* and iterate over `i in range(k*carpetLen, N)`\n\nThis will result in out of bounds errors if `numCarpets*carpetLen > len(floor)`, but that\'s easy to handle: **if we can cover the whole array with the given carpets then we can return `0` immediately.**\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n        # DP? limited carpets\n\n        # top-down DFS\n        \n        # @cache\n        # def minVisible(i: int, k: int) -> int:\n        #     """min visible in 0..i after k carpets"""\n        #     # if we use a carpet at i answer is minVisible(i-len, k-1)\n        #     # if not then if the floor is white here it\'s 1 plus minVisible(i-1)[k]\n\n        if numCarpets*carpetLen >= len(floor): return 0\n\n        N = len(floor)\n        prev = list(accumulate(int(c) for c in floor))\n        curr = [0]*N\n        for k in range(1, numCarpets+1):\n            curr[k*carpetLen-1] = 0 # lay end-to-end\n            for i in range(k*carpetLen, N):\n                curr[i] = min(curr[i-1] + int(floor[i]), prev[i-carpetLen])\n\n            curr, prev = prev, curr\n\n        return prev[-1]\n```
['Python3']