tiling-a-rectangle-with-the-fewest-squares

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a rectangle of size <code>n</code> x <code>m</code>, return the minimum number of integer-sided squares that tile the rectangle.

&nbsp;
Example 1:

<img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_11_1592.png" style="width: 154px; height: 106px;" />

<pre>
Input: n = 2, m = 3
Output: 3
Explanation: <code>3</code> squares are necessary to cover the rectangle.
<code>2</code> (squares of <code>1x1</code>)
<code>1</code> (square of <code>2x2</code>)</pre>

Example 2:

<img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_22_1592.png" style="width: 224px; height: 126px;" />

<pre>
Input: n = 5, m = 8
Output: 5
</pre>

Example 3:

<img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_33_1592.png" style="width: 224px; height: 189px;" />

<pre>
Input: n = 11, m = 13
Output: 6
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n, m &lt;= 13</code></li>
</ul>

tilingRectangle

Tiling a Rectangle with the Fewest Squares

Selling Pieces of Wood

selling-pieces-of-wood

卖木头块

Backtracking

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

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/25/sample_11_1592.png" style="height: 106px; width: 154px;" />

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

示例 2：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/25/sample_22_1592.png" style="height: 126px; width: 224px;" />

<pre>
输入：n = 5, m = 8
输出：5
</pre>

示例 3：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/25/sample_33_1592.png" style="height: 189px; width: 224px;" />

<pre>
输入：n = 11, m = 13
输出：6
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n, m &lt;= 13</code></li>
</ul>