C++ Easy to understand, with explanation and optimizations. DP
Hello, while it may seem like a difficult one, the fourth question can be done with an almost bruteforce approach with some optimizations.\n\nLet dp[i][j] denot
Hello, while it may seem like a difficult one, the fourth question can be done with an almost bruteforce approach with some optimizations.\n\nLet dp[i][j] denote the maximum number of ones we can cover with i carpets till index j(**with current carpet ending exactly at index j**). Assuming that the current carpet ends at exactly j *greatly simplifies* the problem\n\nNow, dp[i][j]= number of ones in string[j:j-len]+ max(dp[i-1][j-len], dp[i-1][j-len-1],....dp[i-1][0])\n\nOptimizations:\nWe store this max part of previous iteration of i till j-len in a helper variable. (prevmax)\nWe use prefix sum array to calculate number of white blocks in a range in O(1) time\nWe only need the ith and i-1th rows of the dp array, so space can be reduced (didn\'t do it due to time constraints during contest)\n\n```\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        int dp[1001][1001]={0};\n        int pre[1000]={0};\n        if(floor[0]==\'1\')pre[0]=1;\n        for(int i=1;i<floor.size();i++){\n            pre[i]+=pre[i-1];\n            if(floor[i]==\'1\')pre[i]++;\n        }\n        for(int i=1;i<=numCarpets;i++){\n            int prevmax=0;\n            for(int j=0;j<floor.size();j++){\n                if(j<carpetLen) dp[i][j]=pre[j];\n                else{\n                    prevmax=max(prevmax,dp[i-1][j-carpetLen]);\n                    dp[i][j]=pre[j]-pre[j-carpetLen]+prevmax;\n                }\n            }\n        }\n        int ans=0;\n        for(int i=0;i<floor.size();i++)ans=max(ans,dp[numCarpets][i]);\n        return pre[floor.size()-1]-ans;\n    }\n};\n```\n
['Dynamic Programming', 'C']