# 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([0] * m, 0, n, global_best)
return global_best[0]
def _fill(self, heights, squares_so_far, target_height, global_best):
if squares_so_far >= global_best[0]:
return
basin_height = min(heights)
if basin_height == target_height:
global_best[0] = 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]
# Code (C++)
Approach 1:
Approach 2: