leetcode 1240

问题

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

Example 1:

img

1
2
3
4
5
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:

img

1
2
Input: n = 5, m = 8
Output: 5

Example 3:

img

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

Constraints:

  • 1 <= n <= 13
  • 1 <= m <= 13

分析

自底向上依次填充，每次寻找最左边一个填充最小的列，然后从大到小依次尝试可以填充的正方形。保存一个表示每列高度的数组来表示当前的填充状态。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 尚未增加状态记忆剪枝
// 相同状态出现时，若该状态已经能达到的值小于等于当前值则剪枝
// long key = 0, base = m + 1;
// for (int i = 1; i <= n; i++) {
//     key += h[i] * base;
//     base *= m + 1;
// }
class Solution {
public:
    int tilingRectangle(int n, int m) {
        if (n == m) return 1;
        if (n > m) swap(n, m);
        vector<int> h(n, 0);
        int ans = 13*13;
        dfs(ans, 0, h, m, n);
        return ans;
    }
    void dfs(int &ans, int cur, vector<int> &h, int m, int n) {
        if (cur >= ans) return;
        int pos = 0;
        for (int i = 0; i < n; ++i)
            if (h[i] < h[pos]) pos = i;

        if (h[pos] == m) {
            ans = min(ans, cur);
            return;
        }
        int e = pos;
        while (e < n && h[e] == h[pos] && h[pos]+e-pos+1 <= m)
            e++;
        for (int i = --e; i >= pos; --i) {
            int add = i-pos+1;
            for (int j = pos; j <= i; ++j) {
                h[j] += add;
            }
            dfs(ans, cur+1, h, m, n);
            for (int j = pos; j <= i; ++j) {
                h[j] -= add;
            }
        }
        return;
    }
};