💥 Beats 100% on runtime [EXPLAINED]
Intuition\nMinimize the number of white tiles visible after covering them with carpets. Carpets can overlap, and each carpet can cover a fixed number of consecu
# Intuition\nMinimize the number of white tiles visible after covering them with carpets. Carpets can overlap, and each carpet can cover a fixed number of consecutive tiles. The problem can be tackled using dynamic programming, where we explore whether it\'s better to cover certain tiles or leave them uncovered.\n\n# Approach\nUse a DP table where each entry represents the minimum number of white tiles left uncovered after covering some portion of the floor with a certain number of carpets; we fill this table by deciding at each tile whether to place a carpet and cover a set of white tiles or to leave the current tile uncovered.\n\n# Complexity\n- Time complexity:\nO(n * numCarpets), where n is the length of the floor, because we compute the result for each tile and each number of carpets using a table of size n * numCarpets.\n\n- Space complexity:\nO(n * numCarpets), due to the storage of the DP table and prefix sum array, which have dimensions based on the floor length and the number of carpets.\n\n# Code\n```csharp []\npublic class Solution {\n    private int[] prefix;\n    private int[,] dp;\n\n    public int MinTiles(int n, string floor, int numCarpets, int carpetLen) {\n        if (n < 0) {\n            return 0;\n        }\n        if (numCarpets == 0) {\n            return prefix[n];\n        }\n        if (dp[n, numCarpets] != -1) {\n            return dp[n, numCarpets];\n        }\n        int cover = MinTiles(n - carpetLen, floor, numCarpets - 1, carpetLen);\n        int notCover = MinTiles(n - 1, floor, numCarpets, carpetLen) + (floor[n] == \'1\' ? 1 : 0);\n        dp[n, numCarpets] = Math.Min(cover, notCover);\n        return dp[n, numCarpets];\n    }\n\n    public int MinimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        if (numCarpets * carpetLen >= floor.Length) {\n            return 0;\n        }\n\n        int n = floor.Length;\n        prefix = new int[n];\n        dp = new int[n, numCarpets + 1];\n\n        // Initialize the dp array with -1\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j <= numCarpets; j++) {\n                dp[i, j] = -1;\n            }\n        }\n\n        // Fill the prefix array\n        if (floor[0] == \'1\') {\n            prefix[0] = 1;\n        }\n        for (int i = 1; i < n; i++) {\n            prefix[i] = (floor[i] == \'1\') ? 1 : 0;\n            prefix[i] += prefix[i - 1];\n        }\n\n        // Call the MinTiles function starting from the last index\n        return MinTiles(n - 1, floor, numCarpets, carpetLen);\n    }\n}\n\n```
['String', 'Dynamic Programming', 'Prefix Sum', 'C#']