<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:
		# a square is given
        if n==m: return 1
		#minimize cache and state
        if n>m: n,m = m,n
        cache = {}
        
        def dfs(heights):
            if all(h==m for h in heights): return 0
            if heights in cache: return cache[heights]
            
            hmin = m+1
            cache[heights] = m*n
			#find the lowest height
            for i,h in enumerate(heights):
                if h<hmin:
                    hmin=h
                    start=i
            new_heights = list(heights)
			#try filling the cavity with tiles of increasing sizes and return the minimum
            for end in range(start,n):
                if new_heights[end]==hmin and heights[end]+end-start+1<=m:
                    new_heights[start:end+1] = [hmin+end-start+1]*(end-start+1)
                    cache[heights]=min(cache[heights],dfs(tuple(new_heights))+1)
                else:
                    break
            return cache[heights]
        
        return dfs(tuple([0]*n))        
551