What is the key pattern for solving the Tiling a Rectangle with the Fewest Squares problem?

The key pattern is backtracking with pruning, where you explore all possible square sizes and placements while pruning unnecessary paths to minimize the number of squares.

How can I optimize my backtracking solution?

You can optimize by using pruning to eliminate paths that cannot lead to a solution better than the current one and applying memoization to avoid redundant calculations.

Can memoization help with large inputs?

Yes, memoization is especially helpful for large inputs as it stores intermediate results, reducing the number of redundant calculations during backtracking.

How do I handle edge cases in this problem?

Edge cases typically involve small rectangles, where no tiling is possible, or when the solution requires minimal squares. Ensure your algorithm can handle these scenarios by carefully managing the search space.

What other tiling problems are similar to this one?

Other tiling problems, such as tiling with different shapes or restricted tile sizes, also rely on backtracking and dynamic programming techniques to efficiently explore solution spaces.

#1240

Hard

auto_awesome回溯·pruning

LeetCode 题解工作台

铺瓷砖

给定一个大小为 n x m 的长方形，返回贴满矩形所需的整数边正方形的最小数量。示例 1：输入： n = 2, m = 3 输出： 3 解释：需要 3 个正方形来覆盖长方形。 2 个 1x1 的正方形 1 个 2x2 的正方形示例 2：输入： n = 5, m = 8 输出： 5 示例 3…

回溯

题目描述

给定一个大小为 n x m 的长方形，返回贴满矩形所需的整数边正方形的最小数量。

示例 1：

输入：n = 2, m = 3
输出：3
解释：需要 3 个正方形来覆盖长方形。
     2 个 1x1 的正方形
     1 个 2x2 的正方形

示例 2：

输入：n = 5, m = 8
输出：5

示例 3：

输入：n = 11, m = 13
输出：6

提示：

1 <= n, m <= 13

lightbulb

解题思路

方法一：递归回溯 + 状态压缩

我们可以按位置进行递归回溯，过程中我们用一个变量 $t$ 记录当前使用的瓷砖数。

如果 $j = m$ ，即第 $i$ 行已经被完全填充，则递归到下一行，即 $(i + 1, 0)$ 。
如果 $i = n$ ，则表示所有位置都已经被填充，我们更新答案并返回。
如果当前位置 $(i, j)$ 已经被填充，则直接递归到下一个位置 $(i, j + 1)$ 。
否则，我们枚举当前位置 $(i, j)$ 可以填充的最大正方形的边长 $w$ ，并将当前位置 $(i, j)$ 到 $(i + w - 1, j + w - 1)$ 的位置全部填充，然后递归到下一个位置 $(i, j + w)$ 。在回溯时，我们需要将当前位置 $(i, j)$ 到 $(i + w - 1, j + w - 1)$ 的位置全部清空。

由于每个位置只有两种状态：填充或者未填充，因此我们可以使用一个整数来表示当前位置的状态。我们使用一个长度为 $n$ 的整数数组 $filled$ ，其中 $filled[i]$ 表示第 $i$ 行的状态。如果 $filled[i]$ 的第 $j$ 位为 $1$ ，则表示第 $i$ 行第 $j$ 列已经被填充，否则表示未填充。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        def dfs(i: int, j: int, t: int):
            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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to implement backtracking efficiently
question_mark
Understanding of pruning in search algorithms
question_mark
Knowledge of dynamic programming optimizations like memoization

warning

常见陷阱

外企场景

error
Ignoring pruning, leading to unnecessary computation
error
Not using memoization, causing redundant calculations
error
Improperly handling edge cases like small rectangles

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing rectangles with larger dimensions
arrow_right_alt
Implementing iterative solutions for large inputs
arrow_right_alt
Exploring other tiling shapes or configurations beyond squares

help

常见问题

外企场景

继续练习

#1239 串联字符串的最大长度 #1238 循环码排列 #1255 得分最高的单词集合