# 1240. Tiling a Rectangle with the Fewest Squares

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

Example 1:

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

Example 2:

``````Input: n = 5, m = 8
Output: 5
``````

Example 3:

``````Input: n = 11, m = 13
Output: 6
``````

Constraints:

• `1 <= n, m <= 13`

``````         m
--------------
|n-i         |
n |------------|
| i |   m-i  |
--------------

m
--------------
|n-i|        |
n |----        |
| i |   m-i  |
--------------
``````

``````class Solution {
public:
int tilingRectangle(int n, int m) {
if (n > m) return tilingRectangle(m, n);
vector<vector<int>> memo(n + 1, vector<int>(m + 1));
return helper(n, m, memo);
}
int helper(int n, int m, vector<vector<int>>& memo) {
if (n > m) return helper(m, n, memo);
if (n == 0) return 0;
if (n == m) return 1;
if (n == 1) return m;
if (memo[n][m] > 0) return memo[n][m];
int res = INT_MAX;
for (int i = 1; i <= n; ++i) {
res = min(res, 1 + helper(n - i, m, memo) + helper(i, m - i, memo));
res = min(res, 1 + helper(n, m - i, memo) + helper(n - i, i, memo));
for (int j = n - i + 1; j < m - i && j < n; ++j) {
res = min(res, 2 + helper(n - i, m - j, memo) + helper(i + j - n, m - i - j, memo) + helper(n - j, m - i, memo));
}
}
return memo[n][m] = res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1240

https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/

https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/discuss/967635/Java-100-Recursion-with-Memoization.

https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/discuss/791203/C%2B%2BDynamic-Programming-Backtracking-with-Figure.Explained.(100-faster)

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation