Dp with prefix sum
i, where we are\nj, carpets we have left\n\n# Code\n\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n   
i, where we are\nj, carpets we have left\n\n# Code\n```\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n        n = len(floor)\n        psum = [0]\n        for a in floor:\n            if a == \'1\':\n                psum.append(psum[-1]+1)\n            else:\n                psum.append(psum[-1])\n        @cache\n        def dp(i,j):\n            if i >= n:\n                return 0\n            if j == 0:\n                return psum[-1] - psum[i]\n            res = int(floor[i]==\'1\')+dp(i+1,j)\n            res = min(res,dp(i+carpetLen,j-1))\n            return res\n        return dp(0,numCarpets)\n\n        \n```
['Dynamic Programming', 'Prefix Sum', 'Python3']