C++ Knapsack Memoization
\nclass Solution {\n    int n;\n    vector<int> suffix;\n    vector<vector<int>> memo;\npublic:\n    \n    int doit(string& floor, int carp, int len, int ind) {
```\nclass Solution {\n    int n;\n    vector<int> suffix;\n    vector<vector<int>> memo;\npublic:\n    \n    int doit(string& floor, int carp, int len, int ind) {\n        if (ind >= n)   return 0;\n        if (carp == 0)  return suffix[ind]; // if no carpets are left then all the white tiles from current index to the last will be visible\n        if (memo[carp][ind] != -1)  return memo[carp][ind];\n        int a = doit(floor, carp-1, len, ind+len); // carpet is used\n        int b = doit(floor, carp, len, ind+1) + (floor[ind] == \'1\'); // carpet is not used\n        return memo[carp][ind] = min(a, b);\n    }\n        \n    int minimumWhiteTiles(string floor, int carp, int len) {\n        \n        n = size(floor);\n        suffix.resize(n+1, 0);\n        memo.resize(carp+1, vector<int>(n+1, -1));\n        suffix[n-1] = (floor[n-1] == \'1\');\n        for (int i=n-2; ~i; i--)\n            suffix[i] = suffix[i+1] + (floor[i] == \'1\');\n        \n        return doit(floor, carp, len, 0);\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C']