Memory-Optimized DP
It feels like there could be some clever way to lay carpets, but there isn\'t. We need to search for an optimal solution.\n\n> Note: problem constrains give it 
It feels like there could be some clever way to lay carpets, but there isn\'t. We need to search for an optimal solution.\n\n> Note: problem constrains give it away.\n\nWe start with the top-down approach, and then convert it to the bottom-up one. By analyzing the tabulation, we can reduce the memory usage to O(n). The runtime for the final, memory-optimized bottom-up approach is 120 ms.\n\n#### Top-Down\nFor the search, we can skip positions with black tiles.\n**C++**\n```cpp\nint dp[1001][1001] = {};\nint dfs(string &floor, int i, int n, int len) {\n    if (n < 0)\n        return floor.size();\n    if (floor.size() - i <= n * len)\n        return 0;\n    if (floor[i] == \'0\')\n        return dfs(floor, i + 1, n, len);\n    if (dp[i][n] == 0)\n        dp[i][n] = 1 + min(1 + dfs(floor, i + 1, n, len), dfs(floor, i + len, n - 1, len)); \n    return dp[i][n] - 1;\n}\nint minimumWhiteTiles(string floor, int numCarpets, int len) {\n    return dfs(floor, 0, numCarpets, len);\n} \n```\n\n#### Bottom-Up\n**C++**\n```cpp\nint dp[1001][1001] = {};\nint minimumWhiteTiles(string floor, int numCarpets, int len) {\n    for (int i = floor.size() - 1; i >= 0; --i) {\n        dp[i][0] = dp[i + 1][0] + (floor[i] == \'1\');\n        for (int c = 1; c <= numCarpets; ++c)\n            dp[i][c] = min(dp[i + 1][c] + (floor[i] == \'1\'), dp[min(1000, i + len)][c - 1]);\n    }\n    return dp[0][numCarpets];\n}  \n```\n\n#### Memory-Optimized Bottom-Up DP\nWe can rearrange loops from the solution above so that the first loop iterates through carpets. That way, we only need to store tabulation values for the current and previous step. \n\n**C++**\n```cpp\nint minimumWhiteTiles(string floor, int numCarpets, int len) {\n    int sz = floor.size(), dp[2][1001] = {};\n    for (int i = 0; i < sz; ++i)\n        dp[0][i + 1] += dp[0][i] + (floor[i] == \'1\');  \n    for (int c = 1; c <= numCarpets; ++c)\n        for (int i = 0; i < sz; ++i)\n            dp[c % 2][i + 1] = min(dp[c % 2][i] + (floor[i] == \'1\'),\n                dp[(c + 1) % 2][max(0, i + 1 - len)]);\n    return dp[numCarpets % 2][sz];\n} \n```
[]