# 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: