Simple Explanation and Solution (Memoization) [Python]
Intuition\nBacktracking memoization solution. At every step we either place a carpet or don\'t - we do whatever minimizes the number of exposed white tiles. For
# Intuition\nBacktracking memoization solution. At every step we either place a carpet or don\'t - we do whatever minimizes the number of exposed white tiles. For every tile we make a binary choice, which means complexity $O(2^n)$, but with memoization we reduce that to $O(n^2)$.\n\n# Complexity\n- Time complexity: $$\\mathcal{O}(n^2)$$\n- Space complexity: $$\\mathcal{O}(n \\cdot k)$$\n\nWhere $n = nums.length$ and $k = numCarpets$.\n\n# Code\n```\nclass Solution:\n\n    def minimumWhiteTiles(self, floor: str, carpets: int, length: int) -> int:\n        \n        floor = [int(tile) for tile in floor]\n        \n        @cache # O(floor.length * numCarpets) memory\n        def backtrack(i: int, carpets: int) -> int:\n\n            # there is no more floor to carpet\n            if i >= len(floor):\n                return 0\n\n            # we have no more carpets to place\n            if carpets == 0:\n                # this tile and all remaining tiles could be visible\n                return floor[i] + backtrack(i + 1, carpets)\n            else: \n                # we have some carpets to place\n                # we can either:\n                #   1. place a carpet to hide the tiles under it (ignore them, skip one carpet-length ahead), or\n                #   2. keep the carpet, saving one for later but exposing the current tile (which could be white)\n                # simply do both and pick whichever one is better\n                place = backtrack(i + length, carpets - 1)\n                dont = floor[i] + backtrack(i + 1, carpets)\n                return min(place, dont)\n            \n        return backtrack(0, carpets)\n```
['Dynamic Programming', 'Backtracking', 'Recursion', 'Memoization', 'Python', 'Python3']