Recursion + memoization + Time-Saver Trick
\nclass Solution {\npublic: \n    int dp[1001][1001];\n    int helper(string &floor, int idx, int numCarpets, int len)\n    {\n        if(idx >= floor.size())\n
```\nclass Solution {\npublic: \n    int dp[1001][1001];\n    int helper(string &floor, int idx, int numCarpets, int len)\n    {\n        if(idx >= floor.size())\n            return 0;\n\t\t\t\n        int &ans = dp[idx][numCarpets]; //reference variable so that we dont have to write this again \n        \n        if(ans != -1) //if state already calculated no need to calculate again directly return its value\n            return ans;\n        \n        int op1 = INT_MAX, op2 = INT_MAX;\n\t\t//when you dont use a new carpet from the current index\n        op1 = (floor[idx] == \'1\') + helper(floor, idx+1, numCarpets, len);\n\t\t//when you use a new carpet from the current index\n        if(numCarpets > 0)\n        op2 = helper(floor, idx+len, numCarpets-1, len);\n        return ans = min(op1, op2);\n    }\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetlen) {\n        memset(dp, -1, sizeof(dp));\n        return helper(floor, 0, numCarpets, carpetlen);\n    }\n};\n\n```\nThe question could be solved in a recursive manner where you just need to know the index and the number of carpets left, now at any index we have two options either we can use the available carpets or we can leave this index as it is. We can consider both options and return the minimum of both the available options.\n\nI have used a trick that is I used a reference variable to store dp[idx][numCarpets], now imagine those questions where we have 3 or 4 states and we don\'t want those dp[][][] states again and again. We can simply use reference variables and we can use them our code to save sometime in competitions.\n\nPlease upvote if you have learnt anything from this post.
['Recursion', 'Memoization']