1240：铺瓷砖（2241 分）

2019-10-27 约 398 字预计阅读 1 分钟次阅读

力扣第 160 场周赛第 4 题

题目

给定一个大小为 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

相似问题：

2312：卖木头块（2363 分）

分析

遍历空格子，尝试放正方形，回溯即可
朴素回溯会超时，有两种剪枝方法
- 先计算一个上界
  - 比如若 m>n，直接放一个 n*n 的正方形，递归计算一个解
  - 回溯时超过上界即中断
- 尝试放正方形时，从大到小放
  - 同样的，回溯时超过上界即中断
这里采用第二种，速度更快

解答

 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


```python
class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        g = [[0]*n for _ in range(m)]
        res = inf
        def dfs(i,j,k):
            nonlocal res
            if k>=res or i==m:
                res = min(res,k)
                return
            if j==n:
                dfs(i+1,0,k)
                return
            if g[i][j]:
                dfs(i,j+1,k)
                return
            a = next(a for a in range(n+1) if i+a>=m or j+a>=n or g[i][j+a])
            for x in range(i,i+a):
                for y in range(j,j+a):
                    g[x][y] = 1
            for b in range(a,0,-1):
                dfs(i,j+b,k+1)
                for x in range(i,i+b):
                    g[x][j+b-1] = 0
                for y in range(j,j+b):
                    g[i+b-1][y] = 0
        dfs(0,0,0)
        return res

1

87 ms

目录

1240：铺瓷砖（2241 分）

题目

分析

解答