<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, height: int, width: int) -> int:
        
        # 1. get the min height of the occupiedHeights
        # 2. get it's valley width
        # 3. place all blocks in the valley from len 1 to min(curHeight + width of valley, height)
        #    # update the height of the matrix  and then call the fill recursively
        
        @cache
        def fillSquares(occupiedHeights):
            occupiedHeights = list(occupiedHeights)
            minHeight = float("inf")
            
            left = None
            for index, curHeight in enumerate(occupiedHeights):
                if curHeight < minHeight:
                    minHeight = curHeight
                    left = index

            if minHeight == height:
                # not placing anything anymore
                return 0

            res = float("inf")
            for right in range(left, width):
                if occupiedHeights[right] == minHeight:
                    curWidth = right-left + 1
                    if minHeight + curWidth <= height:
                        occupiedHeights[left:right+1] = [minHeight + curWidth] * curWidth
                        res = min(res, fillSquares(tuple(occupiedHeights)) + 1)
                        #backtrack
                        occupiedHeights[left:right+1] = [minHeight] * curWidth
                else:
                    break
            return res
        
        
        # start from the bottom
        occupiedHeights = [0] * width

        return fillSquares(tuple(occupiedHeights))
853