<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 {
    bool isAvailable( vector<vector<bool>>& dp, int r, int c, int k ) {
        int R = r+k, C = c+k;
        for( int r1=r; r1<R; r1++ )
            for( int c1 = c; c1<C; c1++ ) 
                if( dp[r1][c1] == true )
                    return false;
        return true;
    }

    void fillUp( vector<vector<bool>>& dp, int r, int c, int k, bool val ) {
        int R = r+k, C = c+k;
        for( int r1=r; r1<R; r1++ )
            for( int c1 = c; c1<C; c1++ ) 
                dp[r1][c1] = val;
    }
    
    void computeRes( int r, int c, int& res, int curRes, vector<vector<bool>>& dp ) {
        int R = dp.size(), C = dp.front().size();
        if( curRes >= res )
            return;
        if( c >= C ) {       //  The condition should be c>=C, as we are skipping k cells as a part of optimisation-2.
            computeRes( r+1, 0, res, curRes, dp );
            return;
        }
        if( r == R ) {
            res = min( res, curRes );
            return;
        }
        if( dp[r][c] ) {
            while( c<C and dp[r][c] )   c++;    // Optimisation-1: Skip all the cells which are already filled.
            computeRes( r, c, res, curRes, dp );
            return;
        }
        for( int k=min(R-r,C-c); k>0; k-- ) {
            if( not isAvailable( dp, r, c, k ) )
                break;
            fillUp( dp, r, c, k, true );
            computeRes( r, c+k, res, curRes+1, dp );     // Optimisation-2: use c+k, instead of c+1
            fillUp( dp, r, c, k, false );
        }
    }
public:
    int tilingRectangle(int R, int C) {
        int res = INT_MAX, curRes = 0;
        vector< vector<bool> > dp( R, vector<bool>(C,false) );
        computeRes( 0, 0, res, curRes, dp );
        return res;
    }
};
9900