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