<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:
    int n, m, res;

    int tilingRectangle(int n, int m) {
        this->n = n;
        this->m = m;
        this->res = INT_MAX;
        
        // Dynamic programming for perfect squares (like in problem #279)
        vector<int> dp(n * m + 1, INT_MAX);
        dp[0] = 0; // Base case: 0 area needs 0 squares
        for (int i = 1; i <= n * m; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = min(dp[i], 1 + dp[i - j * j]);
            }
        }

        // Initialize the skyline (array of column heights)
        vector<int> skyline(m, 0); // Initially all columns are empty
        
        // Start DFS with 0 squares used and full area remaining
        dfs(skyline, dp, 0, n * m);
        
        return res;
    }

private:
    // DFS function for filling the rectangle
    void dfs(vector<int>& skyline, const vector<int>& dp, int sqUsed, int remainingArea) {
        // Base case: if there's no area left to fill, check for result
        if (remainingArea == 0) {
            res = min(res, sqUsed);
            return;
        }
        
        // Pruning: If current squares + dp[remainingArea] >= current best result, stop exploring
        if (sqUsed + dp[remainingArea] >= res) return;

        // Find the lowest leftmost valley in the skyline
        int mini = 0;
        int minh = skyline[0];
        for (int i = 0; i < m; i++) {
            if (skyline[i] < minh) {
                mini = i;
                minh = skyline[i];
            }
        }

        // Find the rightmost boundary of the flat valley
        int maxi = mini;
        while (maxi < m && skyline[maxi] == minh) maxi++;
        
        // Try fitting the largest square possible in this valley
        for (int len = min(maxi - mini, n - minh); len > 0; len--) {
            // Add square to the skyline
            for (int i = mini; i < mini + len; i++) {
                skyline[i] += len;
            }

            // Recur with updated state
            dfs(skyline, dp, sqUsed + 1, remainingArea - len * len);

            // Undo the square placement (backtrack)
            for (int i = mini; i < mini + len; i++) {
                skyline[i] -= len;
            }
        }
    }
};

7900