Skip to content

1240. Tiling a Rectangle with the Fewest Squares

  • Time: $O(\max(n, m) \cdot 2^{\max(n, m)})$
  • Space: $O(\max(n, m) \cdot 2^{\max(n, m)})$
 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
 public:
  int tilingRectangle(int n, int m) {
    return tilingRectangle(n, m, 0, vector<int>(m));
  }

 private:
  static constexpr int kBase = 13;
  unordered_map<long, int> dp;

  int tilingRectangle(int n, int m, long hashedHeights, vector<int>&& heights) {
    if (const auto it = dp.find(hashedHeights); it != dp.cend())
      return it->second;

    const auto it = min_element(heights.begin(), heights.end());
    const int minHeight = *it;
    if (minHeight == n)  // All filled
      return 0;

    int ans = m * n;
    const int start = it - heights.begin();
    // Try to put square of different size that doesn't exceed the width/height
    for (int sz = 1; sz <= min(m - start, n - minHeight); ++sz) {
      // heights[start:start + sz] must has the same height
      if (heights[start + sz - 1] != minHeight)
        break;
      // Put a square of size `sz` to cover heights[start:start + sz]
      for (int i = start; i < start + sz; ++i)
        heights[i] += sz;
      ans = min(ans, tilingRectangle(n, m, hash(heights), move(heights)));
      for (int i = start; i < start + sz; ++i)
        heights[i] -= sz;
    }

    return dp[hashedHeights] = 1 + ans;
  }

  long hash(const vector<int>& heights) {
    long hashed = 0;
    for (int i = heights.size() - 1; i >= 0; --i)
      hashed = hashed * kBase + heights[i];
    return hashed;
  }
};

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
  public int tilingRectangle(int n, int m) {
    return tilingRectangle(n, m, 0, new int[m]);
  }

  private static final int kBase = 13;
  private Map<Long, Integer> dp = new HashMap<>();

  private int tilingRectangle(int n, int m, long hashedHeights, int[] heights) {
    if (dp.containsKey(hashedHeights))
      return dp.get(hashedHeights);

    final int minHeight = Arrays.stream(heights).min().getAsInt();
    if (minHeight == n) // All filled
      return 0;

    int ans = m * n;
    int start = -1;

    for (int i = 0; i < m; ++i)
      if (heights[i] == minHeight) {
        start = i;
        break;
      }

    // Try to put square of different size that doesn't exceed the width/height
    for (int sz = 1; sz <= Math.min(m - start, n - minHeight); ++sz) {
      // heights[start:start + sz] must has the same height
      if (heights[start + sz - 1] != minHeight)
        break;
      // Put a square of size `sz` to cover heights[start:start + sz]
      for (int i = start; i < start + sz; ++i)
        heights[i] += sz;
      ans = Math.min(ans, tilingRectangle(n, m, hash(heights), heights));
      for (int i = start; i < start + sz; ++i)
        heights[i] -= sz;
    }

    dp.put(hashedHeights, 1 + ans);
    return 1 + ans;
  }

  private long hash(int[] heights) {
    long hashed = 0;
    for (int i = heights.length - 1; i >= 0; --i)
      hashed = hashed * kBase + heights[i];
    return hashed;
  }
}

 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:
  def tilingRectangle(self, n: int, m: int) -> int:
    @functools.lru_cache(None)
    def dp(heights: int) -> int:
      minHeight = min(heights)
      if minHeight == n:  # All filled
        return 0

      ans = m * n
      heightsList = list(heights)
      start = heightsList.index(minHeight)  # Start index

      # Try to put square of different size that doesn't exceed the width and width
      for sz in range(1, min(m - start + 1, n - minHeight + 1)):
        # heights[start:start + sz] must has the same height
        if heights[start + sz - 1] != minHeight:
          break
        # Put a square of size `sz` to cover heights[start:start + sz]
        heightsList[start:start + sz] = [minHeight + sz] * sz
        ans = min(ans, dp(tuple(heightsList)))

      return 1 + ans

    return dp(tuple([0] * m))