C++  Fixed-length Sliding Window + DP
See my latest update in repo LeetCode\n\n## Solution 1. Fixed-length Sliding Window + DP\n\nIntuition:\n\n1. Use a sliding window of length carpetLen to compute
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Fixed-length Sliding Window + DP\n\n**Intuition**:\n\n1. Use a sliding window of length `carpetLen` to compute a `cover` array where `cover[i]` is the number of white tiles covered by a carpet placed ending at `floor[i]`.\n2. Use DP to calculate the maximum coverable white tiles using `numCarpets` carpets.\n\n**Algorithm**:\n\n**Fixed-length Sliding Window**:\n\nKeep a rolling sum `white` as the number of white tiles within the sliding window.\n\nFor each `i` in range `[0, N)`, we:\n* increment `white` if `s[i] == \'1\'`\n* decrement `white` if `s[i - len] == \'1\'`\n* Set `cover[i] = white`.\n\n**DP**:\n\nLet `dp[i][j + 1]` be the maximum number of coverable white tiles where `1 <= i <= numCarpet` is number of carpets used and `0 <= j < N` is the last index where we can place carpet.\n\nAll `dp` values are initialized as `0`s.\n\nFor each `dp[i][j + 1]`, we have two options:\n1. Don\'t place carpet at index `j`. `dp[i][j+1] = dp[i][j]`\n2. Place carpet ending at index `j` covering `cover[j]` white tiles. And we can place `i-1` carpets at or before `j-carpetLen`. So, `dp[i][j+1] = dp[i-1][j-carpetLen+1] + cover[j]`.\n\n```\ndp[i][j + 1] = max(\n                    dp[i][j],                                                                   // don\'t place carpet at index `j`\n                    (j - carpetLen + 1 >= 0 ? dp[i - 1][j - carpetLen + 1] : 0) + cover[j]      // place carpet at index `j`\n                  )\n```\n\n`dp[numCarpet][N]` is the maximum number of white titles coverable. The answer is the number of total white tiles minus `dp[numCarpet][N]`. \n\n```cpp\n// OJ: https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/\n// Author: github.com/lzl124631x\n// Time: O(N * numCarpet)\n// Space: O(N * numCarpet)\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpet, int carpetLen) {\n        int N = floor.size(), sum = 0;\n        vector<int> cover(N);\n        for (int i = 0, white = 0; i < N; ++i) {\n            sum += floor[i] - \'0\';\n            white += floor[i] - \'0\';\n            if (i - carpetLen >= 0) white -= floor[i - carpetLen] - \'0\'; \n            cover[i] = white;\n        }\n        vector<vector<int>> dp(numCarpet + 1, vector<int>(N + 1));\n        for (int i = 1; i <= numCarpet; ++i) {\n            for (int j = 0; j < N; ++j) {\n                dp[i][j + 1] = max(dp[i][j], (j - carpetLen + 1 >= 0 ? dp[i - 1][j - carpetLen + 1] : 0) + cover[j]);\n            }\n        }\n        return sum - dp[numCarpet][N];\n    }\n};\n```\n\nWe can reduce the space complexity to `O(N)` by using rolling arrays.\n\n```cpp\n// OJ: https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/\n// Author: github.com/lzl124631x\n// Time: O(N * numCarpet)\n// Space: O(N)\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpet, int carpetLen) {\n        int N = floor.size(), sum = 0;\n        vector<int> cover(N);\n        for (int i = 0, white = 0; i < N; ++i) {\n            sum += floor[i] - \'0\';\n            white += floor[i] - \'0\';\n            if (i - carpetLen >= 0) white -= floor[i - carpetLen] - \'0\'; \n            cover[i] = white;\n        }\n        vector<int> dp(N + 1);\n        for (int i = 1; i <= numCarpet; ++i) {\n            vector<int> next(N + 1);\n            for (int j = 0; j < N; ++j) {\n                next[j + 1] = max(next[j], (j - carpetLen + 1 >= 0 ? dp[j - carpetLen + 1] : 0) + cover[j]);\n            }\n            swap(dp, next);\n        }\n        return sum - dp[N];\n    }\n};\n```
[]