Leetcode 1240. Tiling a Rectangle with the Fewest Squares
The problem requires us to find the minimum number of squares with sides of integer length that can be used to completely cover a rectangle of size n x m. Note that the size of the rectangle is 13 x 13 at the most.
Let's take an example to illustrate it. Suppose the dimensions of the rectangle are 5x8. To cover this rectangle, the minimum possible number of squares would be 5. The illustration below displays how this could be done using 4 squares of size 2x2 and 1 square of size 1x1.
1 2 34x4 4x4 44x4 4x4 5_______ 64x4 4x4 74x4 4x4 81x1
So, the output in this case would be 5.
Approach of the Solution
The solution uses the technique of dynamic programming. It first fills the rectangle as much as possible with the largest possible square, and then recursively fills the leftover space with more squares. Since the maximum size of the rectangle is relatively small, it is suitable for a depth-first search with memoization to find the optimal solution.
tilingRectangle(n, m, 0, vector<int>(m)) starts the recursion. The arguments represent the dimensions of the rectangle and an array indicating the current heights of columns in the rectangle. The hash of the heights array is used for memoizing the results, avoiding excessive recomputation of the same states.
tilingRectangle() function, if all heights are equal to
n this means the rectangle is completely filled and no more squares are needed. Otherwise, a square of maximum possible size is placed at the position with minimum height, and the heights are updated accordingly. The recursion then proceeds with the updated heights. The minimum value from all these recursive calls is then taken and 1 is added (for the current square) to get the final answer which is stored in a memoization table.
hash() function is used to convert the heights array to a unique number because arrays cannot be key of unordered map. This function represents the current state of the rectangle.
This solution works because it explores all possible ways to fill the rectangle and then selects the way which uses the minimum number of squares.
Got a question? Ask the Teaching Assistant anything you don't understand.