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

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Can you use backtracking to solve this problem ?.

Suppose you've placed a bunch of squares. Where is the natural spot to place the next square ?.

The maximum number of squares to be placed will be ≤ max(n,m).

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>

第 160 场周赛

weekly-contest-160

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/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/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/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>

铺瓷砖

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

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

 

示例 1：

[https://assets.leetcode.cn/aliyun-lc-upload/uploads/2019/10/25/sample_11_1592.png]


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

示例 2：

[https://assets.leetcode.cn/aliyun-lc-upload/uploads/2019/10/25/sample_22_1592.png]


输入：n = 5, m = 8
输出：5


示例 3：

[https://assets.leetcode.cn/aliyun-lc-upload/uploads/2019/10/25/sample_33_1592.png]


输入：n = 11, m = 13
输出：6


 

提示：

 * 1 <= n, m <= 13