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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<pre>
<strong>Input:</strong> n = 2, m = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> <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>

<p><strong class="example">Example 2:</strong></p>

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

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

<p><strong class="example">Example 3:</strong></p>

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

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        glob_res = [n * m]
        mem = {}

        @cache
        def fill(hs, sq_placed):
            if hs in mem:
                return sq_placed + mem[hs]
            min_i = 0
            for i, h in enumerate(hs):
                if h < hs[min_i]:
                    min_i = i
            if hs[min_i] == m:
                glob_res[0] = min(glob_res[0], sq_placed)
                mem[hs] = 0
                return sq_placed
            if sq_placed + 1 > glob_res[0]:
                return 1e9
            last_min_i = min_i
            while last_min_i + 1 < len(hs) and hs[last_min_i + 1] == hs[min_i]:
                last_min_i += 1
            sq_max_sz = min(last_min_i - min_i + 1, m - hs[min_i])
            res = 1e9
            for sz in range(sq_max_sz, 0, -1):
                nhs = list(hs)
                nhs[min_i:min_i + sz] = [hs[min_i] + sz] * sz
                res = min(res, fill(tuple(nhs), sq_placed + 1))
            mem[hs] = res - sq_placed
            return res

        hs = tuple([0] * n)
        return fill(hs, 0)
508