# 2209. Minimum White Tiles After Covering With Carpets

## Approach 1: Top-down

• Time: $O(n \cdot \texttt{numCarpets})$
• Space: $O(n \cdot \texttt{numCarpets})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) { // dp[i][j] := min # of visible white tiles of floor[i:] // After covering at most j carpets dp.resize(floor.length() + 1, vector(numCarpets + 1, kMax)); return minimumWhiteTiles(floor, 0, numCarpets, carpetLen); } private: static constexpr int kMax = 1000; vector> dp; int minimumWhiteTiles(const string& floor, int i, int j, int carpetLen) { if (j < 0) return kMax; if (i >= floor.length()) return 0; if (dp[i][j] != kMax) return dp[i][j]; return dp[i][j] = min( minimumWhiteTiles(floor, i + carpetLen, j - 1, carpetLen), minimumWhiteTiles(floor, i + 1, j, carpetLen) + floor[i] - '0'); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) { // dp[i][j] := min # of visible white tiles of floor[i:] // After covering at most j carpets dp = new int[floor.length() + 1][numCarpets + 1]; Arrays.stream(dp).forEach(A -> Arrays.fill(A, kMax)); return minimumWhiteTiles(floor, 0, numCarpets, carpetLen); } private static final int kMax = 1000; private int[][] dp; int minimumWhiteTiles(final String floor, int i, int j, int carpetLen) { if (j < 0) return kMax; if (i >= floor.length()) return 0; if (dp[i][j] != kMax) return dp[i][j]; return dp[i][j] = Math.min(minimumWhiteTiles(floor, i + carpetLen, j - 1, carpetLen), minimumWhiteTiles(floor, i + 1, j, carpetLen) + floor.charAt(i) - '0'); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int: kMax = 1000 # dp(i, j) := min # Of visible white tiles of floor[i:] # After covering at most j carpets @functools.lru_cache(None) def dp(i: int, j: int) -> int: if j < 0: return kMax if i >= len(floor): return 0 return min(dp(i + carpetLen, j - 1), dp(i + 1, j) + int(floor[i])) return dp(0, numCarpets) 

## Approach 2: Bottom-up

• Time: $O(n \cdot \texttt{numCarpets})$
• Space: $O(n \cdot \texttt{numCarpets})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) { const int n = floor.length(); // dp[i][j] := min # of visible white tiles of floor[i:] // After covering at most j carpets vector> dp(n + 1, vector(numCarpets + 1)); for (int i = n - 1; i >= 0; --i) dp[i][0] = floor[i] - '0' + dp[i + 1][0]; for (int i = n - 1; i >= 0; --i) for (int j = 1; j <= numCarpets; ++j) { const int cover = i + carpetLen < n ? dp[i + carpetLen][j - 1] : 0; const int skip = floor[i] - '0' + dp[i + 1][j]; dp[i][j] = min(cover, skip); } return dp[0][numCarpets]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) { final int n = floor.length(); // dp[i][j] := min # of visible white tiles of floor[i:] // After covering at most j carpets int[][] dp = new int[n + 1][numCarpets + 1]; for (int i = n - 1; i >= 0; --i) dp[i][0] = floor.charAt(i) - '0' + dp[i + 1][0]; for (int i = n - 1; i >= 0; --i) for (int j = 1; j <= numCarpets; ++j) { final int cover = i + carpetLen < n ? dp[i + carpetLen][j - 1] : 0; final int skip = floor.charAt(i) - '0' + dp[i + 1][j]; dp[i][j] = Math.min(cover, skip); } return dp[0][numCarpets]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int: n = len(floor) # dp[i][j] := min # Of visible white tiles of floor[i:] # After covering at most j carpets dp = [[0] * (numCarpets + 1) for _ in range(n + 1)] for i in reversed(range(n)): dp[i][0] = int(floor[i]) + dp[i + 1][0] for i in reversed(range(n)): for j in range(1, numCarpets + 1): cover = dp[i + carpetLen][j - 1] if i + carpetLen < n else 0 skip = int(floor[i]) + dp[i + 1][j] dp[i][j] = min(cover, skip) return dp[0][numCarpets]