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

        if m == n: return 1
        if m == 1: return n
        if n == 1: return m

        heights = [0]*m
        global best, count
        best = n*m
        count = 0

        def explore():
            global best, count

            lo = min(heights)

            if lo == n:
                best = min(count, best)
                return

            if count >= best-1:
                return

            i = heights.index(lo)
            j = i+1
            while j < m and heights[j] == lo: j += 1
            s = min(j-i, n-lo)

            for w in range(s, 0, -1):
                count += 1
                for c in range(i, i+w):
                    heights[c] += w

                explore()

                count -= 1
                for c in range(i, i+w):
                    heights[c] -= w

        explore()

        return best
78