Thoroughly Explained C++ code
Intuition\nDon\'t think about the overlapping of the carpets because it will be taken care at the end because it can be folded from the end side as well.\n\n# A
# Intuition\nDon\'t think about the overlapping of the carpets because it will be taken care at the end because it can be folded from the end side as well.\n\n# Approach\nWe will use a array to store the prefix sum and the find the maximum amount of white tiles that can be removed and then subtract the tiles from total number of white tiles that will give us the minimum number of white tiles.\nTo find the number of white tiles that can be removed from placing the carpet starting at index i will be -\nprefix[i + carpetLen - 1] - prefix[n - 1];\nThe above formula gives us the number of white tiles that are placed between index "i" and "i + carpetLen - 1" and that is covered by the carpet.\nWhen the "i + carpetLen - 1" is going out of bound we will use prefix[n - 1] instead of prefix[i + carpetLen - 1] because prefix[n - 1] is the maximum tiles.\n\n# Complexity\n- Time complexity:\n    O(N*C) where \n    N = Length of floor\n    C = Number of Carpets\n\n- Space complexity:\n    O(N) + O(N*C) + O(N)\n    O(N) for prefix array\n    O(N*C) for dp array\n    O(N) for stack space\n\n    It can be improved by using bottom up DP where we will not use stack space and the DP space can also improve by using two 1D array of size numCarpet instead of using a 2D dp array.\n\n# Code\n```\n\nint solve(vector<int> &prefix, int num, int l, int index, int n, vector<vector<int>> &dp){\n    if(index >= n){\n        return 0;\n    }\n    if(dp[index][num] != -1)return dp[index][num];\n    int inc = 0;\n    if(num > 0){\n        if(index + l - 1 >= n){\n            inc = (prefix[n - 1] - prefix[index - 1]) + solve(prefix, num - 1, l, index + l, n, dp);\n        }\n        else{\n            inc = (prefix[index + l - 1] - prefix[index - 1]) + solve(prefix, num - 1, l, index + l, n, dp);\n        }\n    }\n    int exc = solve(prefix, num, l, index + 1, n, dp);\n    return dp[index][num] = max(inc, exc);\n}\n\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        int n = floor.size();\n        vector<int> prefix(n + 1, 1);\n        int white = 0, j = 1;\n        for(auto i : floor){\n            int x = i - \'0\', y = prefix[j - 1];\n            if(x == 1)white++;\n            prefix[j++] = (x + y);\n        }\n        vector<vector<int>> dp(n + 1, vector<int>(numCarpets + 1, -1));\n        int removedWhite = solve(prefix, numCarpets, carpetLen, 1, n + 1, dp);\n        return white - removedWhite;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'Prefix Sum', 'C++']