✅[Python] Dynamic Programming + Prefix Sum Solution | Explained
So this is a dynamic programming question with a trick.\nYou can guess it using the given constraints.\nThe solution can be divided into two parts:\n  Recursive
So this is a dynamic programming question with a trick.\nYou can guess it using the given constraints.\nThe solution can be divided into two parts:\n*  Recursively find ways to use carpets to cover the floor \n* Optimize using **Prefix Sum** to find the number of white tiles present between two indices of the floor\n\nPlease read through the comments for better understanding!\n```\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n\t\tn = len(floor)\n\t\t#Using memo table to store predefined computations\n        memo = [[-1 for x in range(numCarpets+1)] for x in range(len(floor)+1)] \n        def solve(N,numCarpets):\n\t\t\t#Base Case\n            if N>=n:\n                return 0\n\t\t\t#If calculated previously use that solution\n            if memo[N][numCarpets]!=-1:\n                return memo[N][numCarpets]\n\t\t\t\t\n            used = 0 # If you use the carpet\n            notused = 0 # If you donot use the carpet\n\t\t\t\n            if floor[N]==\'1\': # We might use the carpet in this part\n                if numCarpets>0: #Whether we even have some carpets or not\n\t\t\t\t    """\n\t\t\t\t\tOptimization Part\n\t\t\t\t\tWe are finding the number of ones present in this part of the floor.\n\t\t\t\t\tprefix[lastInd] - Number of ones till lastInd\n\t\t\t\t\tprefix[N] - Number of ones till Nth Index.\n\t\t\t\t\t\n\t\t\t\t\tTheir difference gives us how many ones present between the two.\n\t\t\t\t    """\n                    lastInd = min(N+carpetLen,len(floor)) \n                    ans = prefix[lastInd] - prefix[N]\n                    \n\t\t\t\t\t"""\n\t\t\t\t\tFind the max if we use or donot use carpet at this index\n\t\t\t\t\tIf we do we add  --- ans and decrement remaining carpets\n\t\t\t\t\telse we donot\n\t\t\t\t\t"""\n                    used = max(solve(N+carpetLen,numCarpets-1)+ans,solve(N+1,numCarpets))\n                            \n                else:\n                    used = 0\n            \n            else:\n\t\t\t#If we donot use the carpet although I feel this might be redundant code\n                notused = solve(N+1,numCarpets)\n            \n\t\t\t#Using max function to find the number of white tiles removed\n            memo[N][numCarpets] = max(used,notused)\n            return memo[N][numCarpets]\n\t\t\n\t\t#Total White tiles\n        ones = 0\n        for x in floor:\n            if x == \'1\':\n                ones+=1\n        \n\t\t#Using Prefix array to store number of ones till i th index\n        prefix = [0]*(n+1)\n        for i in range(1,n+1):\n            if floor[i-1]==\'1\':\n                prefix[i] = prefix[i-1]+1\n            else:\n                prefix[i] = prefix[i-1]\n\t\t\t\t\n       \n        removed = solve(0,numCarpets)\n        \n        return ones-removed\n```
['Dynamic Programming', 'Prefix Sum', 'Python']