Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1240.html

1240. Tiling a Rectangle with the Fewest Squares

Level

Hard

Description

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

Example 1:

Image text

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:

Image text

Input: n = 5, m = 8

Output: 5

Example 3:

Image text

Input: n = 11, m = 13

Output: 6

Constraints:

  • 1 <= n <= 13
  • 1 <= m <= 13

Solution

Use dynamic programming. Create a 2D array dp of n + 1 rows and m + 1 columns, where dp[i][j] represents the minimum number of squares required to tile the i * j rectangle.

Obviously, if i == j, dp[i][j] = 1. Otherwise, the rectangle can be split by a horizontal line or a vertical line, which leads to two smaller rectangles, or a square may be put in the middle. For each case, calculate the minimum number of squares needed.

Finally, return dp[n][m].

  • class Solution {
        public int tilingRectangle(int n, int m) {
            int[][] dp = new int[n + 1][m + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (i == j)
                        dp[i][j] = 1;
                    else {
                        dp[i][j] = Integer.MAX_VALUE;
                        int rowStart = 1, rowEnd = i / 2;
                        for (int row = rowStart; row <= rowEnd; row++)
                            dp[i][j] = Math.min(dp[i][j], dp[row][j] + dp[i - row][j]);
                        int columnStart = 1, columnEnd = j / 2;
                        for (int column = columnStart; column <= columnEnd; column++)
                            dp[i][j] = Math.min(dp[i][j], dp[i][column] + dp[i][j - column]);
                        for (int row = 1; row <= i; row++) {
                            for (int column = 1; column <= j; column++) {
                                for (int side = Math.min(row, column) - 1; side > 0; side--)
                                    dp[i][j] = Math.min(dp[i][j], 1 + dp[row - side][column] + dp[i - row + side][column - side] + dp[i - row][j - column + side] + dp[row][j - column]);
                            }
                        }
                    }
                }
            }
            return dp[n][m];
        }
    }
    
  • class Solution {
    public:
        int tilingRectangle(int n, int m) {
            memset(filled, 0, sizeof(filled));
            this->n = n;
            this->m = m;
            ans = n * m;
            dfs(0, 0, 0);
            return ans;
        }
    
    private:
        int filled[13];
        int n, m;
        int ans;
    
        void dfs(int i, int j, int t) {
            if (j == m) {
                ++i;
                j = 0;
            }
            if (i == n) {
                ans = t;
                return;
            }
            if (filled[i] >> j & 1) {
                dfs(i, j + 1, t);
            } else if (t + 1 < ans) {
                int r = 0, c = 0;
                for (int k = i; k < n; ++k) {
                    if (filled[k] >> j & 1) {
                        break;
                    }
                    ++r;
                }
                for (int k = j; k < m; ++k) {
                    if (filled[i] >> k & 1) {
                        break;
                    }
                    ++c;
                }
                int mx = min(r, c);
                for (int w = 1; w <= mx; ++w) {
                    for (int k = 0; k < w; ++k) {
                        filled[i + w - 1] |= 1 << (j + k);
                        filled[i + k] |= 1 << (j + w - 1);
                    }
                    dfs(i, j + w, t + 1);
                }
                for (int x = i; x < i + mx; ++x) {
                    for (int y = j; y < j + mx; ++y) {
                        filled[x] ^= 1 << y;
                    }
                }
            }
        }
    };
    
  • class Solution:
        def tilingRectangle(self, n: int, m: int) -> int:
            def dfs(i, j, t):
                nonlocal ans
                if j == m:
                    i += 1
                    j = 0
                if i == n:
                    ans = t
                    return
                if filled[i] >> j & 1:
                    dfs(i, j + 1, t)
                elif t + 1 < ans:
                    r = c = 0
                    for k in range(i, n):
                        if filled[k] >> j & 1:
                            break
                        r += 1
                    for k in range(j, m):
                        if filled[i] >> k & 1:
                            break
                        c += 1
                    mx = r if r < c else c
                    for w in range(1, mx + 1):
                        for k in range(w):
                            filled[i + w - 1] |= 1 << (j + k)
                            filled[i + k] |= 1 << (j + w - 1)
                        dfs(i, j + w, t + 1)
                    for x in range(i, i + mx):
                        for y in range(j, j + mx):
                            filled[x] ^= 1 << y
    
            ans = n * m
            filled = [0] * n
            dfs(0, 0, 0)
            return ans
    
    
  • func tilingRectangle(n int, m int) int {
    	ans := n * m
    	filled := make([]int, n)
    	var dfs func(i, j, t int)
    	dfs = func(i, j, t int) {
    		if j == m {
    			i++
    			j = 0
    		}
    		if i == n {
    			ans = t
    			return
    		}
    		if filled[i]>>j&1 == 1 {
    			dfs(i, j+1, t)
    		} else if t+1 < ans {
    			var r, c int
    			for k := i; k < n; k++ {
    				if filled[k]>>j&1 == 1 {
    					break
    				}
    				r++
    			}
    			for k := j; k < m; k++ {
    				if filled[i]>>k&1 == 1 {
    					break
    				}
    				c++
    			}
    			mx := min(r, c)
    			for w := 1; w <= mx; w++ {
    				for k := 0; k < w; k++ {
    					filled[i+w-1] |= 1 << (j + k)
    					filled[i+k] |= 1 << (j + w - 1)
    				}
    				dfs(i, j+w, t+1)
    			}
    			for x := i; x < i+mx; x++ {
    				for y := j; y < j+mx; y++ {
    					filled[x] ^= 1 << y
    				}
    			}
    		}
    	}
    	dfs(0, 0, 0)
    	return ans
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions