1240. Tiling a Rectangle with the Fewest Squares¶
题目信息¶
- 题号:
1240
- 难度:
Hard
- 主题:
回溯、状态压缩、矩形铺砌
- 原题:
- 重点:
使用边平行于矩形边界、边长为正整数的正方形无重叠铺满
n x m矩形,并最小化正方形数量
题目重述¶
给定矩形的整数边长 n 和 m。可以使用任意数量、任意整数边长的正方形,每个正方形必须完全位于矩形内,正方形之间不能重叠,所有正方形的并集必须恰好覆盖整个矩形。
请返回完成铺砌所需正方形的最少数量。
1 <= n, m <= 13。
自建示例¶
非正方形矩形需要组合不同尺寸:
输入:n = 3, m = 4
输出:4
解释:可以使用一个 3 x 3 正方形和三个 1 x 1 正方形;无法只用三个正方形完整覆盖该矩形。
高度为一时只能使用单位正方形:
输入:n = 1, m = 5
输出:5
解释:任何可放入的正方形边长都只能为 1,因此需要五个。