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