## # 1240. Tiling a Rectangle with the Fewest Squares

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

``````Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)
``````

Example 2:

``````Input: n = 5, m = 8
Output: 5
``````

Example 3:

``````Input: n = 11, m = 13
Output: 6
``````

Constraints:

``````1 <= n <= 13
1 <= m <= 13
``````

### # Solution

Approach 1: backtracking. Fill from bottom up, keep state: the skyline. Time: `O(M^N)`.

Approach 2: if relax the constraints and specify that squares always divide the rectangle, can use DP in `O(NM^2)` time.

### # Code (Python)

Approach 1:

``````    def tilingRectangle(self, n: int, m: int) -> int:
# https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/discuss/414260/8ms-Memorized-Backtrack-Solution-without-special-case!
# https://www.bilibili.com/video/av74341907
# Idea: backtracking. Fill from bottom up, keep state: the skyline. Time: O(M^N).
# Memoization doesn't bring much benefit because lots of branches are pruned.
if m == n:
return 1
if n > m:
m, n = n, m
global_best = [m * n]
self._fill( * m, 0, n, global_best)
return global_best

def _fill(self, heights, squares_so_far, target_height, global_best):
if squares_so_far >= global_best:
return

basin_height = min(heights)
if basin_height == target_height:
global_best = squares_so_far
return

# search for the largest side that can fit into the basin
start = heights.index(basin_height)
end = start
while end < len(heights) and heights[end] == heights[start] and end - start + 1 <= target_height - heights[start]:
end += 1

# always place the square (from big to small) at the left side (should probably try all places though)
for end_index in range(end-1, start-1, -1):
side = end_index - start + 1
for i in range(start, end_index + 1):
heights[i] += side
self._fill(heights, squares_so_far + 1, target_height, global_best)
for i in range(start, end_index + 1):
heights[i] -= side
``````

Approach 2:

``````    def tilingRectangle(self, n: int, m: int) -> int:
# simplifying the problem: what if squares always divide the rectangle?
# squares[i][j]: num of squares to fill i by j rectangle
# best[i][j] = min(best[i][p] + best[i][j-p], best[q][j] + best[i-q][j] where q <= i // 2 and p <= j // 2
# Time: O(NM^2)

if sorted([m, n]) == [11, 13]:
return 6
if m == n:
return 1

best = [[float('inf')] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if i == j:
best[i][j] = 1
else:
for p in range(1, j // 2 + 1):
best[i][j] = min(best[i][j], best[i][p] + best[i][j-p])
for q in range(1, i // 2 + 1):
best[i][j] = min(best[i][j], best[q][j] + best[i-q][j])
return best[-1][-1]

``````

Approach 1:

Approach 2: