<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:
    # Function to get the hash key for rem_squares array
    def get_key(self, rem_squares, B):
        base = 1
        key = 0
        for i in range(B):
            key += rem_squares[i] * base
            base *= (B + 1)
        return key

    # Recursive function to find the minimum number of square cuts
    # for a given rem_squares array
    def solve(self, rem_squares, A, B, dp):
        # Check if we have previously calculated the answer for the same state
        key = self.get_key(rem_squares, B)
        if key in dp:
            return dp[key]

        max_rem_squares = 0
        start = end = 0

        # Find the starting point of the minimum height
        for i in range(B):
            if rem_squares[i] > max_rem_squares:
                max_rem_squares = rem_squares[i]
                start = i

        # If max remaining squares = 0, then we have already cut the entire paper
        if max_rem_squares == 0:
            return 0

        end = start
        new_rem_squares = rem_squares[:]
        
        ans = float('inf')
        # Find the ending point of the minimum height
        while end < B:
            # Length of edge of square from start till current end
            square_edge = end - start + 1

            # If the current column does not have maximum remaining squares
            # or if it's impossible to cut a square of size square_edge, then break out of the loop
            if new_rem_squares[end] != max_rem_squares or new_rem_squares[end] - square_edge < 0:
                break

            # If we can cut a square of size square_edge, update the remaining squares
            for i in range(start, end + 1):
                new_rem_squares[i] = max_rem_squares - square_edge

            # Find the solution for new remaining squares
            ans = min(ans, 1 + self.solve(new_rem_squares, A, B, dp))
            end += 1
        
        dp[key] = ans
        return ans
    def tilingRectangle(self, A: int, B: int) -> int:
        # If the given rectangle is a square
        if A == B:
            return 1

        # Initialize remaining squares = A for all the B columns
        rem_squares = [A] * B

        dp = {}
        return self.solve(rem_squares, A, B, dp)
810