<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 dp(self, n, m, heights, memo):

        if heights in memo:
            return memo[heights]
        
        start = 0
        min_height = n

        for i in range(len(heights)):
            if heights[i] < min_height:
                min_height = heights[i]
                start = i
        
        if min_height == n:
            # rectangle is filled with squares
            return 0


        ans = sys.maxsize
        
        new_heights = list(heights)

        for end in range(start, m):
            if new_heights[end] == min_height:
                square_edge = end - start + 1
                if square_edge + min_height <= n:
                    new_heights[start:end+1] = [square_edge + min_height] * square_edge
                    ans = min(ans, self.dp(n, m, tuple(new_heights), memo) + 1)
            else:
                break
        
        memo[heights] = ans
        return ans

    def tilingRectangle(self, n: int, m: int) -> int:
        return self.dp(n, m, tuple([0] * m), {})

    # def tilingRectangle(self, n: int, m: int) -> int:
    #     # dp handle special case
    #     # complexity: time O(m*n*n), mem O(m*n)
    #     if (n == 11 and m == 13) or (n == 13 and m == 11): return 6
        
    #     dp = [[float("inf")] * (n+1) for _ in range(m+1)]

    #     for i in range(1, m+1):
    #         for j in range(1, n+1):
    #             if i == j:
    #                 dp[i][j] = 1
    #             else:
    #                 for k in range(1, i//2+1):
    #                     dp[i][j] = min(dp[i][j], dp[k][j] + dp[i-k][j]) 
    #                 for k in range(1, j//2+1):
    #                     dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j-k])
    #     return dp[m][n]
681