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
26
27
class Solution {
 public:
  int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
    vector<vector<int>> mem(floor.length() + 1,
                            vector<int>(numCarpets + 1, kMax));
    return minimumWhiteTiles(floor, 0, numCarpets, carpetLen, mem);
  }

 private:
  static constexpr int kMax = 1000;

  // Returns the minimum number of visible white tiles of floor[i..n) after
  // covering at most j carpets.
  int minimumWhiteTiles(const string& floor, int i, int j, int carpetLen,
                        vector<vector<int>>& mem) {
    if (j < 0)
      return kMax;
    if (i >= floor.length())
      return 0;
    if (mem[i][j] != kMax)
      return mem[i][j];
    return mem[i][j] = min(
               minimumWhiteTiles(floor, i + carpetLen, j - 1, carpetLen, mem),
               minimumWhiteTiles(floor, i + 1, j, carpetLen, mem) + 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
class Solution {
  public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
    int[][] mem = new int[floor.length() + 1][numCarpets + 1];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, MAX));
    return minimumWhiteTiles(floor, 0, numCarpets, carpetLen, mem);
  }

  private static final int MAX = 1000;

  // Returns the minimum number of visible white tiles of floor[i..n) after
  // covering at most j carpets.
  int minimumWhiteTiles(final String floor, int i, int j, int carpetLen, int[][] mem) {
    if (j < 0)
      return MAX;
    if (i >= floor.length())
      return 0;
    if (mem[i][j] != MAX)
      return mem[i][j];
    return mem[i][j] =
               Math.min(minimumWhiteTiles(floor, i + carpetLen, j - 1, carpetLen, mem),
                        minimumWhiteTiles(floor, i + 1, j, carpetLen, mem) + floor.charAt(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
class Solution:
  def minimumWhiteTiles(
      self,
      floor: str,
      numCarpets: int,
      carpetLen: int,
  ) -> int:
    MAX = 1000

    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """
      Returns the minimum number of visible white tiles of floor[i..n) after
      covering at most j carpets.
      """
      if j < 0:
        return MAX
      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] := the minimum number of visible white tiles of floor[i..n)
    // 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] := the minimum number of visible white tiles of floor[i..n)
    // 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
18
19
20
21
22
class Solution:
  def minimumWhiteTiles(
      self,
      floor: str,
      numCarpets: int,
      carpetLen: int,
  ) -> int:
    n = len(floor)
    # dp[i][j] := the minimum number of visible white tiles of floor[i..n)
    # 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]