[Python] short dp, explained
Problem constraints will help you to understand that this problem can be solved with dp. Let the state dp(i, t) be minimum number of white tiles when we allowed
Problem constraints will help you to understand that this problem can be solved with `dp`. Let the state `dp(i, t)` be minimum number of white tiles when we allowed to use `t` number of carpets such that their right (and hence all carpets) lies in `[0, i]`. Then each moment of time we have option to take carpet or do not take it:\n1. If we take, previous state is `dp(i - L, t - 1)`.\n2. If we do not take it, previous state is `dp(i - 1, t) + `int(floor[i] == "1")`.\n\n#### Complexity\nIt is `O(n^2)` for time and space.\n\n#### Code\n```python\nclass Solution:\n    def minimumWhiteTiles(self, floor, k, L):\n        @lru_cache(None)\n        def dp(i, t):\n            if t < 0: return float("inf")\n            if i < 0: return 0\n            return min(dp(i - L, t - 1), dp(i - 1, t) + int(floor[i] == "1"))\n        \n        return dp(len(floor) - 1, k)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']