leetcode 1240. Tiling a Rectangle with the Fewest Squares

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.
Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)
Example 2:

Input: n = 5, m = 8
Output: 5
Example 3:

Input: n = 11, m = 13
Output: 6

解题思路：

class Solution {
public:
    map<long, int> set;
    int res = 100000001;
    int tilingRectangle(int n, int m) {
        if (n == m) return 1;
        if (n > m) {
            int temp = n;
            n = m;
            m = temp;
        }
        int *h = new int[n + 1];
        memset(h, 0, (n + 1) * sizeof(int));
        dfs(n, m, h, 0);
        return res;
    }
private: void dfs(int n, int m, int h[], int cnt) {
        if (cnt >= res) return;
        bool isFull = true;
        int pos = -1, minH = 100000001;
        // 看看数组h是不是满了，没满的话顺便记录一下最低的位置minH和对应的索引pos
        for (int i = 1; i <= n; i++) {
            if (h[i] < m) isFull = false;
            if (h[i] < minH) {
                pos = i;
                minH = h[i];
            }
        }
        // 如果铺满了
        if (isFull) {
            res = min(cnt, res);
            return;
        }
        // 没铺满的话，继续铺
        /* 这里有一个小trick，把整个数组h的状态映射到一个long的整数类型上。
        这个映射是一对一的映射！！！
        具体方法是把数组看成（m+1）进制的数，就可以转化成一个long类型的整数了。
        因为base的选取是（m+1），而数组中的每个数都不超过m，故肯定是一个一对一的映射！
        即不可能存在两个不一样的数组映射到同一个long类型的整数上。
        */
        long key = 0, base = m + 1;
        for (int i = 1; i <= n; i++) {
            key += h[i] * base;
            base *= m + 1;
        }
        if (set.count(key) && set[key] <= cnt) return;
        set[key] = cnt;
        // 找到和pos一样低的末尾位置
        int end = pos;
        while (end + 1 <= n && h[end + 1] == h[pos] && (end + 1 - pos + 1 + minH) <= m) end++;
        // 找到了pos~end这个最低位置的区间后，从end开始，遍历到pos位置，每次铺一块砖。
        // 再继续 dfs
        for (int j = end; j >= pos; j--) {
            int curH = j - pos + 1;
            int next[n + 1];
            memcpy(next, h, (n + 1)*sizeof(int));
            for (int k = pos; k <= j; k++) {
                next[k] += curH;
            }
            dfs(n, m, next, cnt + 1);
        }
    }
};