<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 {
public:
    vector<vector<int>> dp;
    int recurse(int n, int m)
    {
        if(n>m)
        swap(n,m);
        if(dp[n][m]!=-1)
        return dp[n][m];
        if(n==0 || m==0)
        return 0;
        if(n==m)
        return 1;
        if(m==1)
        return n;
        if(n==1)
        return m;
        int ans= INT_MAX;
        for(int i=1;i<=n;i++)
        {
            int ans1 = 1+ recurse(m-i,n) + recurse(m,n-i);
            ans= min(ans, ans1);
            // int ans2= 1+ recurse(i,m-i) + recurse(n-i,i);
            // ans= min(ans, min(ans1,ans2));
            for(int j=n-i+1; j<=n && j+i<=m; j++){
                int ans2= 2+ recurse(n-j,m-i)+recurse(n-i,m-j)+recurse(j-(n-i),(m-j)-i);
                ans= min(ans, ans2);
            }
        }
        dp[n][m]= ans;
        return ans;
    }
    int tilingRectangle(int n, int m) {
        dp.assign(100, vector<int>(100,-1));
        return recurse(n,m);
    }
};
9600