C++ Solution | Top-Down Dynamic Programming | Recursion + Memoization
Iterate over string floor:\n\n- At each index pos in the string floor we have two options:\n\n    - Use a carpet, that starts from the index pos and ends at pos
Iterate over string `floor`:\n\n- At each index `pos` in the string `floor` we have two options:\n\n    - Use a carpet, that starts from the index `pos` and ends at `pos + carpetLength - 1`. All tiles in this part will change to black, hence move to index `pos + carpetLength`\n    - Skip the index and move to next index `pos + 1`. This time the tile at index `pos` will be unchanged, thus add `1` to the answer if it\'s a white tile.\n\n- After either of the options, recursively move to the next index. Return the minimum of the above two options.\n\nBase Case:\n\n- If we have traversed the whole string `floor`, then no white tiles present. Hence return `0`.\n- If we have used all the available carpets, then the remaining string will not change. Hence return the number of `1`\'s in the remaining string. (Store the number of `1`s for the suffix `[i, N]` in the array `suffix` beforehand, instead of finding it again and again).\n\nThere will be repeated subproblems corresponding to index (`pos`) and the number of carpet used (`used`). Hence store the result in the table `dp` and use it to answer repeated problems insetad of going into recursion.\n\n```\nclass Solution {\npublic:\n    int dp[1001][1001];\n    int suffix[1001];\n\n    void findSuffixSum(string& floor) {\n        int n = floor.size();\n        \n        suffix[n - 1] = (floor[n - 1] == \'1\');\n        for (int i = n - 2; i >= 0; i--) {\n            suffix[i] = suffix[i + 1] + (floor[i] == \'1\');\n        }\n    }\n    \n    int solve(string& floor, int numCarpets, int carpetLen, int pos, int used) {\n        if (pos >= floor.size()) {\n            return 0;\n        } else if (used == numCarpets) {\n            return suffix[pos];\n        }\n        \n        if (dp[pos][used] != -1) {\n            return dp[pos][used];\n        }\n\n        return dp[pos][used] = min(solve(floor, numCarpets, carpetLen, pos + carpetLen, used + 1),\n                      (floor[pos] == \'1\') + solve(floor, numCarpets, carpetLen, pos + 1, used));\n    }\n    \n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        memset(dp, -1, sizeof(dp));\n        findSuffixSum(floor);\n        \n        return solve(floor, numCarpets, carpetLen, 0, 0);\n    }\n};\n```
[]