1240. Tiling a Rectangle with the Fewest Squares

题目信息

题号:

1240

难度:

Hard

主题:

回溯、状态压缩、矩形铺砌

原题:

LeetCode 1240

重点:

使用边平行于矩形边界、边长为正整数的正方形无重叠铺满 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,因此需要五个。