C++ | DP | Recursion + Memorization | Easy to Understand
c++\nclass Solution {\npublic:\n    int carpetLen, fLen;\n    vector<int> sum;\n    vector<vector<int>> dp;\n    int solve(int pos, int numCar, string& floor){\
```c++\nclass Solution {\npublic:\n    int carpetLen, fLen;\n    vector<int> sum;\n    vector<vector<int>> dp;\n    int solve(int pos, int numCar, string& floor){\n        if(pos >= fLen){\n            return 0;\n        }\n        \n        if(numCar == 0){\n            return 0;\n        }\n        \n        int &ret = dp[pos][numCar];\n        \n        if(ret != -1){\n            return ret;\n        }\n        \n        int taken = 0, notTaken = 0;\n        int fSum = 0, lSum = 0;\n        \n        fSum = pos > 0 ? sum[pos - 1] : 0;\n        lSum = pos + carpetLen > fLen ? sum[fLen - 1] : sum[pos + carpetLen - 1];\n        \n        taken = lSum - fSum + solve(pos + carpetLen,  numCar - 1, floor);\n        notTaken = solve(pos + 1, numCar, floor);\n        \n        return ret = max(taken, notTaken);\n    }\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        fLen = floor.size();\n        this->carpetLen = carpetLen;\n        sum.resize(fLen + 1, 0);\n        dp.resize(fLen + 1, vector<int> (numCarpets + 1, -1));\n        sum[0] = floor[0] - \'0\';\n        \n        for(int i = 1; i < fLen; i++){\n            sum[i] = sum[i - 1] + (floor[i] - \'0\');\n        }\n        \n        return sum[fLen - 1] - solve(0, numCarpets, floor);\n    }\n};\n```
['Dynamic Programming', 'Memoization']