Skip to content

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<int>(numCarpets + 1, kMax));
    return minimumWhiteTiles(floor, 0, numCarpets, carpetLen);
  }

 private:
  static constexpr int kMax = 1000;
  vector<vector<int>> 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<vector<int>> dp(n + 1, vector<int>(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]