Easy to Understand | C++ | Recursive | Memoization | DP
Intuition\n Describe your first thoughts on how to solve this problem. \nDynamic Programming take and not take simple intuition.\n\n# Approach\n Describe your a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDynamic Programming take and not take simple intuition.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSolved using Dynamic Programming approach.\nThere are 3 case , starting from the first tile \n1. Black tile : skip and move to next tile\n2. White tile not Take : skip and move to next tile\n3. White tile take : use the carpet to cover and move to (curr tile + carpetLen - 1 )th tile\nthen take the max of all.\nWe are taking max because we have to find min uncovered tile, so max covered tile. \n\n# Complexity\n- Time complexity:\nO(floor.length() * numCarpets)\n\n- Space complexity:\nO(floor.length() * numCarpets)\n\n# Code\n```\nclass Solution {\npublic:\n\n    int f(int i, int num, int &len, vector<int> &prefix_floor, string &floor,int &n,vector<vector<int>> &dp){\n        if(i>=n || num==0) return 0;\n        if(dp[i][num]!=-1) return dp[i][num];\n        if(floor[i]==\'0\') return dp[i][num] = f(i+1,num,len,prefix_floor,floor,n,dp);\n        int notTake =  f(i+1,num,len,prefix_floor,floor,n,dp);\n        int bnd = min(i+len-1,n-1);\n        int white = prefix_floor[bnd];\n        if(i!=0) white = white - prefix_floor[i-1];\n        int take = white + f(i+len,num-1,len,prefix_floor,floor,n,dp);\n        return dp[i][num] = max(take,notTake);\n    }\n\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        int n = floor.length();\n        vector<int> prefix_floor;\n        int count = 0;\n        if(floor[0]==\'1\'){\n            prefix_floor.push_back(1);\n            count++;\n        }\n        else prefix_floor.push_back(1);\n        for(int i=1; i<n; i++){\n            if(floor[i]==\'1\'){\n                prefix_floor.push_back(1 + prefix_floor[i-1]);\n                count++;\n            }\n            else{\n                prefix_floor.push_back(prefix_floor[i-1]);\n            }\n        }\n        vector<vector<int>> dp(n,vector<int>(numCarpets+1,-1));\n        return count-f(0,numCarpets,carpetLen,prefix_floor,floor,n,dp);\n    }\n};\n```
['C++']