<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 tilingRectangle(int n, int m) {
    unordered_map<long, int> mem;
    return tilingRectangle(n, m, 0, /*heights=*/vector<int>(m), mem);
  }

 private:
  static constexpr int kBase = 13;

  int tilingRectangle(int n, int m, long hashedHeights, vector<int>&& heights,
                      unordered_map<long, int>& mem) {
    if (const auto it = mem.find(hashedHeights); it != mem.cend())
      return it->second;

    const auto it = ranges::min_element(heights);
    const int minHeight = *it;
    if (minHeight == n)  // All filled.
      return 0;

    int ans = m * n;
    const int start = it - heights.begin();
    // Try to put square of different size that doesn't exceed the width/height.
    for (int sz = 1; sz <= min(m - start, n - minHeight); ++sz) {
      // heights[start..start + sz) must has the same height.
      if (heights[start + sz - 1] != minHeight)
        break;
      // Put a square of size `sz` to cover heights[start..start + sz).
      for (int i = start; i < start + sz; ++i)
        heights[i] += sz;
      ans = min(ans,
                tilingRectangle(n, m, hash(heights), std::move(heights), mem));
      for (int i = start; i < start + sz; ++i)
        heights[i] -= sz;
    }

    return mem[hashedHeights] = 1 + ans;
  }

  long hash(const vector<int>& heights) {
    long hashed = 0;
    for (int i = heights.size() - 1; i >= 0; --i)
      hashed = hashed * kBase + heights[i];
    return hashed;
  }
};
119700