1240. Tiling a Rectangle with the Fewest Squares

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), 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;
  }
};