[Python3]2D DP solution explained
\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n        \n        """\n        dp(pos, numC) -> returns
```\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n        \n        """\n        dp(pos, numC) -> returns min number of white tiles seen from pos to the end of the floor\n                         if we have numC number of carpets left\n        \n        if numC > 0, i.e. we have some carpets remaining:\n            if the tile at index pos is white, then we have two choices, \n                either place a carpet from pos to pos + carpetLen - 1\n                or skip this tile, so number of white tiles increases by one, and calculate the minimum answer from index\n                pos + 1\n            else\n                no need to cover this tile, we can move ahead\n        else:\n            we cannot cover any more white tiles\n            so return number of white tiles from pos to the end of floor\n        \n        \n        time complexity : O(numCarpets * len(floor)) ~ O(n^2)\n        """\n    \n        @lru_cache(None) \n        def dp(pos, numC):\n            if pos >= n:\n                return 0\n            \n            if numC > 0:\n                if floor[pos] == "1":\n                    return min(1 + dp(pos + 1, numC), dp(pos + carpetLen, numC - 1))\n                else:\n                    return dp(pos + 1, numC)\n            else:\n                return ones[pos]\n                \n        \n        n = len(floor)\n        \n        #ones[i] stores the number of white tiles from index i to the end of floor \n        ones = [0 for i in range(n)]\n        ones[-1] = (floor[-1] == "1")\n        \n        for i in range(n-2, -1, -1):\n            ones[i] = ones[i+1] + (floor[i] == "1")\n            \n            \n        return dp(0, numCarpets)\n                \n            \n        \n```
[]