<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>> memo;
	int solve(int n,int m)
	{
		if(memo[n][m]!=-1)
			return memo[n][m];
		if(n==m)
			return 1;
		else if(n==0 || m==0)
			return 0;
		else if(n==1)
			return m;
		int nextn=min(n,m);
		int nextm=max(n,m)-nextn;
		int res=solve(min(nextn,nextm),max(nextn,nextm))+1;     // Default way in Figure 1
		for(int s=nextn-1;s>0;--s)
		{
			int a=max(abs(n-s),abs(m-s));       //larger side
			int b=min(abs(n-s),abs(m-s));       //smaller side
			for(int k=b;k<=a && k<=n;++k)
			{
				int x=min(abs(a-k),abs(b-k)),y=max(abs(a-k),abs(b-k));
				int rect1=solve(min(b,m-k),max(b,m-k));
				int rect2=solve(x,y);
				int rect3=solve(min(n-k,a),max(n-k,a));
				int ans=2+rect1+rect2+rect3;        // here 2 is addded for the 2 rectangle sxs and kxk
				res=min(res,ans);
			}
		}
		memo[n][m]=res;
		return res;
	}
	int tilingRectangle(int n, int m)
	{
		int x=min(n,m),y=max(n,m);
		memo.resize(x+1);
		for(auto& v:memo)
			v.resize(y+1,-1);
		return solve(x,y);
	}
};
7800