<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:
  
        
        
        
# sol: typical backtracking
# principle: try squares (backtracking) in the lowest place (height) in the order of left to right; this ensure unque answers to avoid searching redundant cases.    
# time: not sure about time but clearly the upper limit is min(m,n)^(m*n): each 1*1 box only have a choice from min(m,n) and consider they are independent. A better time is: min(m,n)^ans where ans <= max(m,n) since considering n*1 rectangle the answer is n, considering n*2, the anser is n//2+0or2, etc

        self.ans = m*n #worst answer
        def func(test): #h is height, test is the ans to try
                if test >= self.ans: return
                if all(i==n for i in h): 
                        self.ans = test
                        return
                mi = min(h)
                i = j = h.index(mi)
                while j<m and h[j] == mi: j += 1
# [::-1] is important, because it will get smaller test and "if test >= self.ans: return" will reject small-k results quickly
                for k in range(1, min(j-i, n-mi)+1)[::-1]:
                        h1 = h[i:i+k]
                        h[i:i+k] = [mi+k]*k
                        func(test+1)
                        h[i:i+k] = h1 #backtracking
        h = [0]*m
        func(0) 
        return self.ans
                
                

78