C++ sliding window + dp memo
\nclass Solution {\npublic:\n    // dp memo based on amount of carpets left and current index\n    // first perform a sliding window to determine\n    // how ma
```\nclass Solution {\npublic:\n    // dp memo based on amount of carpets left and current index\n    // first perform a sliding window to determine\n    // how many tiles we cover\n    vector<int> tilesCovered;\n    int l = 1;\n    string s = "";\n    vector<vector<int>> dp;\n    int minimumWhiteTiles(string str, int nc, int len) {\n        tilesCovered = vector<int>(str.size());\n        l = len;\n        s = str;\n        dp = vector<vector<int>>(s.size(), vector<int>(nc + 1, -1));\n        int count = 0;\n        for (int i = 0; i < len && i < s.size(); ++i)\n            count += s[i] == \'1\';\n        tilesCovered[0] = count;\n        for (int i = 1; i < s.size(); ++i){\n            count -= s[i - 1] == \'1\';\n            if (i + len - 1 < s.size())\n                count += s[i + len - 1] == \'1\';\n            tilesCovered[i] = count;\n        }\n        int total = 0;\n        for (auto& c : s) total += c == \'1\';\n        return total - dfs(0, nc);\n    }\n    \n    int dfs(int i, int nc){\n        if (i >= s.size() || nc == 0) return 0;\n        if (dp[i][nc] != -1) return dp[i][nc];\n        dp[i][nc] = max(dfs(i + 1, nc), tilesCovered[i] + dfs(i + l, nc - 1));\n        return dp[i][nc];\n    }\n};\n```
[]