Problem Analysis with formula, dynamic programming (tabulation approach)
At first glance\n\nLet\'s analyze the problem at hand before writing the code. We are given the following inputs:\n\n - Floor, which is a string of characters 0
## At first glance\n\nLet\'s analyze the problem at hand before writing the code. We are given the following inputs:\n\n - **Floor**, which is a string of characters `0` and `1` only.\n\t - **0** denotes a black tile.\n\t - **1** denotes a white tile.\n - **Number of Carpets**, the number of carpets we can place.\n - **Length of Carpet**, the range of a carpet to make everything black.\n\nThe problem is about *minimizing* the number of white tiles. Note the keyword \'minimizing\', which already tells us that this is going to be an optimization problem. You might have guessed it, dynamic programming is the answer to this problem. In specific, we will be using the *tabulation* approach.\n\n<br>\n\n## Problem Analysis\n\n*Note*: From this point forward, we will be referring the **Number of Carpets** as **R** (remaining carpets), **Length of Carpet** as **L** and the **Floor** as **F**.\n\nIn order to find minimum number of white tile possible, we need to find the optimal formula for minimizing the white tile count. After further inspection, we can see that at any index ***i***, we have two possible options:\n\n - Place a carpet on index ***i***, if and only if **R > 0**.\n - Skip the current index.\n\nThis gives us the following optimal formula (denoted as ***opt***):\n\n![image](https://assets.leetcode.com/users/images/2145aad6-6484-40c5-b3f2-e352decf6ff4_1647705757.213423.png)\n\n## Implementation\n\nA reference implementation in C++ is given below:\n\n```cpp\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpets, int L) {\n        vector<vector<int>> opt(floor.size() + 1, vector<int>(numCarpets + 1, 0));\n\n        for (int i = (int) floor.size() - 1; i >= 0; i--) {\n            int F_i = floor[i] - \'0\';\n\n            for (int R = 0; R <= numCarpets; R++) {\n\n                if (R == 0)\n                    opt[i][R] = F_i + opt[i + 1][R];\n                else if (i + L >= floor.size())\n                    opt[i][R] = 0;\n                else\n                    opt[i][R] = min(F_i + opt[i + 1][R], opt[i + L][R - 1]);\n            }\n        }\n\n        return opt[0][numCarpets];\n    }\n};\n```\n\nThis runs in **pseudo-polynomial time O(|F| \xD7 R)** and has a space complexity **O(|F| \xD7 R)**. Note that this is *not polynomial*, but [pseudo-polynomial](https://en.wikipedia.org/wiki/Pseudo-polynomial_time).\n\n\n\n
[]