LeetCode 1240. 铺瓷砖

2022-09-08 HGNULB 约 14 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 1240. 铺瓷砖

题意分析

给一个 n × m 的矩形，用若干个边长为整数的正方形把它完全铺满，正方形之间不能重叠、不能超出边界，问最少需要多少块。

先排除一个非常诱人的错误直觉：很多人会想「每次贪心地放下能放的最大正方形」。这个贪心是错的，最著名的反例就是 11 × 13，贪心会得到 8 块，而最优解是 6 块——最优铺法里存在一块并不紧贴角落的正方形，必须靠全局搜索才能找到。同理，「用欧几里得辗转相除的方式切正方形」也只对某些比例成立，不能作为通解。

也不要指望简单的区间 DP。矩形被放入几块正方形后，剩余区域是一个任意形状的正交多边形，不再是矩形，因此「切一刀分成左右两半」的经典区间 DP 划分方式在这里不成立（最优解可能存在跨越任何一条竖直切线的正方形）。

那么剩下的路只有搜索。约束给了明确许可：1 ≤ n, m ≤ 13。这个上界小得反常，是「允许指数级搜索 + 强剪枝」的标准信号。同时它也提示了状态设计的可行性——如果能把「已铺区域的形状」压缩成一个小状态，就能记忆化。

边界要注意：n == m 时答案显然是 1；n 与 m 谁大谁小不影响答案（矩形可以旋转），可以统一规约成「宽 = 较小边、高 = 较大边」，减少一半状态。

解法：轮廓线回溯 + 记忆化

核心思路

最朴素的搜索是「枚举每个未被覆盖的格子，枚举在它这里放多大的正方形」。瓶颈有两个：一是同一种铺法会以不同的放置顺序被搜到无数遍（k 块正方形有 k! 种放置次序），搜索树严重冗余；二是「剩余区域」用二维布尔网格表示，无法哈希去重。

第一个瓶颈的破法是固定放置顺序。观察到：任何一种合法铺法中，当前所有未覆盖格子里「最靠上、再最靠左」的那个格子，必然是某块正方形的左上角。既然它一定要被某块正方形以左上角的身份覆盖，那我们就规定每一步都只在这个位置放，只枚举放多大。这样每种铺法在搜索树中只会以唯一一条路径出现，k! 的重复被彻底消除。这是「铺砖 / 拼图」类搜索的通用套路。

第二个瓶颈的破法是换一种状态表示。注意到如果始终在「最低最左」处放置，那么已铺区域永远是每列从底部（这里以「高度」计）连续堆起来的形状——不会出现悬空的洞。于是整个已铺形状可以用一个长度为 width 的数组 heights[col]（第 col 列已铺到的高度）完整描述，这就是轮廓线。轮廓线把二维形状压成了一维向量，既好比较也好哈希。

状态定义与不变量：heights[0..width-1] 表示当前轮廓，不变量是「已铺区域恰好等于各列从 0 到 heights[col] 的并集，且其中没有空洞」。这条不变量由「每次都在最低列放置且要求覆盖的各列高度相等」两个条件共同保证——正方形放上去后，被覆盖的那几列整齐地升高同样的量，轮廓仍然是无洞的阶梯形。

每一步的动作：找出 heights 中的最小值 minHeight 及其最靠左的下标 start，正方形必须以 (start, minHeight) 为左下角放置。边长 size 的三个上界是——不能越过右边界（width - start）、不能超出矩形顶部（height - minHeight）、覆盖的连续列必须都恰好等于 minHeight（否则会与已铺部分重叠）。

终止与剪枝：当 minHeight == height 时所有列都铺满，用当前块数更新答案。两条剪枝缺一不可——(1) 最优性剪枝 used >= best 时立刻返回，因为再放下去只会更差；(2) 记忆化剪枝，用一个哈希表记录「到达某个轮廓时用过的最少块数」，若曾以不超过当前的块数到过同一轮廓，当前分支不可能更优，直接砍掉。

枚举边长时从大到小，目的是尽快让 best 降下来，让后续的 used >= best 剪枝更有力——这不影响正确性，只影响速度，但在本题是能否通过的关键。

解题步骤

特判 n == m 返回 1，并把较小边规约为 width、较大边规约为 height。为什么要规约：矩形旋转后答案不变，统一方向能让不同输入共享同一份状态空间；更实际的好处是 heights 数组长度取较小的那条边，编码后的状态更短。

best 初始化为 n * m。为什么这个值一定安全：全部用 1 × 1 铺是永远合法的方案，块数正是 n * m，所以它是一个有效上界，任何搜索到的解都不会更差，最优性剪枝从第一步起就有意义。

进入 dfs 先做最优性剪枝 used >= best。为什么放在最前面：这一步是常数代价，能在做任何昂贵操作（编码、扫描）之前砍掉整条分支。

再做记忆化剪枝：把 heights 编码成一个整数 state，若 seen[state] <= used 则返回，否则写入 seen[state] = used。为什么比较的是「块数」而不是简单的「访问过」：同一个轮廓可以由不同的铺法到达，块数少的那条显然更有前途；只有当本次到达比历史记录更省，才值得继续往下搜。写成「访问过就剪」会误杀更优的路径。

编码用 height + 1 进制。为什么：每列高度的取值范围是 0..height，共 height + 1 种，用它做基数能保证不同轮廓映射到不同整数（这是标准的混合基数编码）。width ≤ 13、height ≤ 13 时最大约 $14^{13} \approx 8 \times 10^{14}$，在 64 位范围内，所以用 long / int64 存。

线性扫描找最小高度与其最左下标。为什么必须取最左：这是「唯一化放置顺序」的一部分，若在多个等高列里随意挑一个，同一铺法又会被多条路径搜到，剪枝效果大打折扣。

minHeight == height 即铺满，此时更新 best = used 并返回。为什么能直接赋值而不用取 min：入口处的 used >= best 剪枝已经保证了走到这里的 used 严格小于 best。

计算最大可放边长：先取 min(width - start, height - minHeight) 两个几何上界，再从左往右检查连续列是否都等于 minHeight，一旦出现不等就把上界砍到那之前。为什么第三个条件必不可少：若某列已经高于 minHeight，正方形放上去会与已铺的部分重叠，方案非法。

从大到小枚举边长，放置 → 递归 → 恢复。放置就是把 [start, start + size) 这几列的高度各加 size，恢复就是各减 size。为什么恢复范围必须与放置范围逐列对应：heights 是全局共享的可变状态，少恢复一列就会让兄弟分支看到一个被污染的轮廓，结果彻底错乱。

以 n = 2、m = 3 走一遍（答案是 3）。规约后 width = 2、height = 3，heights = [0, 0]，best = 6。

dfs(used = 0)：minHeight = 0、start = 0。几何上界 min(2 - 0, 3 - 0) = 2；两列高度都是 0，所以 maxSize = 2。

先试 size = 2：heights 变为 [2, 2]，递归 used = 1。此时 minHeight = 2、start = 0，上界 min(2, 3 - 2) = 1，只能放 size = 1：heights = [3, 2]，递归 used = 2。这时 minHeight = 2、start = 1，上界 min(2 - 1, 1) = 1，放 size = 1 得 heights = [3, 3]，递归 used = 3。minHeight == 3 == height，铺满，best = 3。

逐层回溯并恢复 heights，回到最外层继续试 size = 1：heights = [1, 0]，递归 used = 1。这条分支往下至少还要再放 3 块（剩余是一个 L 形），当 used 涨到 3 时 used >= best 立刻剪断，不再展开。

搜索结束，返回 best = 3，对应铺法是一个 2 × 2 加两个 1 × 1。

顺带看剪枝的价值：如果去掉 used >= best，1 × 1 那条分支会把 2 × 3 的所有铺法枚举一遍；如果去掉记忆化，轮廓 [1, 1] 会分别经由「放一个 1×1 再放一个 1×1」的两种列序各到达一次，规模稍大时这类重复呈指数增长。

代码实现

class Solution {
    private int width;
    private int height;
    private int best;
    private Map<Long, Integer> seen;

    public int tilingRectangle(int n, int m) {
        if (n == m) {
            return 1;
        }

        width = Math.min(n, m);
        height = Math.max(n, m);
        best = n * m;
        seen = new HashMap<>();

        dfs(new int[width], 0);
        return best;
    }

    private void dfs(int[] heights, int used) {
        if (used >= best) {
            return;
        }

        long state = encode(heights);
        Integer oldUsed = seen.get(state);
        if (oldUsed != null && oldUsed <= used) {
            return;
        }
        seen.put(state, used);

        int minHeight = height;
        int start = 0;
        for (int col = 0; col < width; col++) {
            if (heights[col] < minHeight) {
                minHeight = heights[col];
                start = col;
            }
        }

        if (minHeight == height) {
            best = used;
            return;
        }

        int maxSize = getMaxSize(heights, start, minHeight);
        for (int size = maxSize; size >= 1; size--) {
            // 在最低轮廓处放一个 size * size 的正方形。
            for (int col = start; col < start + size; col++) {
                heights[col] += size;
            }

            dfs(heights, used + 1);

            for (int col = start; col < start + size; col++) {
                heights[col] -= size;
            }
        }
    }

    private int getMaxSize(int[] heights, int start, int minHeight) {
        int maxSize = Math.min(width - start, height - minHeight);
        for (int size = 1; size <= maxSize; size++) {
            if (heights[start + size - 1] != minHeight) {
                return size - 1;
            }
        }
        return maxSize;
    }

    private long encode(int[] heights) {
        long state = 0;
        long base = height + 1L;
        for (int value : heights) {
            state = state * base + value;
        }
        return state;
    }
}

func tilingRectangle(n int, m int) int {
    if n == m {
        return 1
    }

    width := n
    height := m
    if width > height {
        width, height = height, width
    }

    best := n * m
    heights := make([]int, width)
    seen := make(map[int64]int)

    var encode func() int64
    encode = func() int64 {
        state := int64(0)
        base := int64(height + 1)
        for _, value := range heights {
            state = state*base + int64(value)
        }
        return state
    }

    var getMaxSize func(start int, minHeight int) int
    getMaxSize = func(start int, minHeight int) int {
        maxSize := width - start
        if height-minHeight < maxSize {
            maxSize = height - minHeight
        }
        for size := 1; size <= maxSize; size++ {
            if heights[start+size-1] != minHeight {
                return size - 1
            }
        }
        return maxSize
    }

    var dfs func(used int)
    dfs = func(used int) {
        if used >= best {
            return
        }

        state := encode()
        if oldUsed, ok := seen[state]; ok && oldUsed <= used {
            return
        }
        seen[state] = used

        minHeight := height
        start := 0
        for col := 0; col < width; col++ {
            if heights[col] < minHeight {
                minHeight = heights[col]
                start = col
            }
        }

        if minHeight == height {
            best = used
            return
        }

        maxSize := getMaxSize(start, minHeight)
        for size := maxSize; size >= 1; size-- {
            // 在最低轮廓处放一个 size * size 的正方形。
            for col := start; col < start+size; col++ {
                heights[col] += size
            }

            dfs(used + 1)

            for col := start; col < start+size; col++ {
                heights[col] -= size
            }
        }
    }

    dfs(0)
    return best
}

复杂度分析

时间复杂度：指数级，理论上界是轮廓状态数 $O((\text{height}+1)^{\text{width}})$ 乘以每个状态的分支数 $O(\text{width})$，再乘以每次编码与扫描的 $O(\text{width})$。凭什么实际能过：n, m ≤ 13 让 width ≤ 13，且真实可达的轮廓（无洞的阶梯形、总面积不超过矩形）远少于理论上界；再叠加「used >= best 最优性剪枝」和「同轮廓劣解剪枝」，实测搜索节点数是可控的常数量级。

空间复杂度：$O(\text{width} \cdot S)$，S 是被记忆化的轮廓数。凭什么：heights 数组只有一份、大小 width；递归深度不超过 best，也就是不超过 n * m；主要开销来自 seen 哈希表，每条记录存一个 64 位编码和一个块数。

关键点总结

遇到「铺满 / 拼图 / 覆盖」类搜索，第一件事是唯一化放置顺序：规定每步只填「最靠上再最靠左」的未覆盖位置。这一招把 k! 的顺序冗余压成 1，是这类题从超时到可过的分水岭，比任何微观优化都重要。

轮廓线（每列已填高度）是二维覆盖问题的标准状态压缩：它把不规则的二维形状压成一维向量，从而可以哈希、可以记忆化。看到「网格 + 逐格填充 + 需要去重」就该想到它。

记忆化的键值语义要想清楚：这里存的是「到达该状态的最小代价」而非「是否访问过」，剪枝条件是 旧代价 <= 新代价。代价型搜索的记忆化必须带上代价比较，否则会误杀更优路径。

贪心在本题是错的，11 × 13 就是反例。面试中如果先提贪心，务必主动说明它会失败并给出这个反例——能说出反例比背对解法更能体现功底。

n, m ≤ 13 这种小得反常的约束是出题人在明说「请用指数级搜索」。先读约束再选算法，可以避免在不存在的多项式解上浪费时间。

分支枚举顺序不影响正确性但极大影响剪枝效率：从大到小试边长能更快压低 best。这是「先找到一个好解，再用它剪枝」的通用思路，与分支限界法同源。

易错点总结

改用「每次放最大正方形」的贪心：n = 11, m = 13 会得到 8 块，而正确答案是 6 块。这个反例必须记住，它是本题存在的全部理由。

不检查覆盖列的高度是否一致就放置：轮廓为 [0, 2] 时若在 start = 0 放边长 2 的正方形，它会与第 1 列已铺的部分重叠，铺出的方案根本不合法，却仍被计入答案，结果偏小。

最小高度取到了非最左的那一列：把扫描写成 heights[col] <= minHeight 会让 start 停在最右侧的等高列上，同一种铺法经由不同列序被重复搜索，剪枝失效，n = 13, m = 11 直接超时。

回溯时恢复范围写错，例如恢复循环写成 col < start + maxSize 而非 start + size：兄弟分支看到的 heights 被污染，n = 2, m = 3 都可能算出小于 3 的荒谬答案。

记忆化只记「访问过」不记块数：轮廓 [1, 1] 第一次由 5 块到达并被标记，之后由 2 块到达的更优路径被误剪，最终答案偏大。

记忆化的剪枝方向写反成 oldUsed >= used 才返回：这会把更优的新路径剪掉、保留更差的旧路径，答案系统性偏大。

编码基数取成 height 而不是 height + 1：高度可以取到 height 本身，共 height + 1 个取值；基数少 1 会让 [0, 3] 与 [1, 0] 这类不同轮廓映射到同一个整数（height = 3 时都是 3），发生哈希碰撞后错误剪枝，答案偏大。

编码用 int 存：width = 13、height = 13 时状态值约 $8 \times 10^{14}$，int 直接溢出并循环回绕，不同轮廓被当成同一个状态，剪枝乱套。

best 初值设成 Integer.MAX_VALUE：本身不会错，但会让最优性剪枝在找到第一个解之前完全失效；更糟的是有人顺手写成一个偏小的猜测值（比如 4），那样所有合法解都会被 used >= best 剪光，返回这个错误初值。

漏掉 n == m 的特判又把 heights 长度取成 0：width = min(n, m) 在正常输入下至少是 1，但若误写成 n - m 之类的表达式，数组长度为 0 会让 minHeight 保持初值 height 而立刻判定「铺满」，返回 0。

误以为可以按竖直切线做区间 DP：11 × 13 的最优解中存在跨越每一条竖直切线的正方形，任何「切成左右两块分别求解再相加」的写法都会得到 8 而不是 6。

相似题目

题目	难度	考察点
37. 解数独	困难	同为「固定顺序填格 + 回溯」，但约束来自行列宫的互斥而非几何拼接
51. N 皇后	困难	逐行放置天然唯一化了顺序，冲突判定用列与两条对角线的集合
473. 火柴拼正方形	中等	一维版的「恰好填满」，靠排序降序 + 跳过等长重复值剪枝
698. 划分为k个相等的子集	中等	同样需要消除「桶之间的对称性」，手法是只往第一个空桶里放
1681. 最小不兼容性	困难	用位掩码枚举子集完成分组，是「状态压缩 + 最优代价记忆化」的另一种形态
847. 访问所有节点的最短路径	困难	状态压缩配 BFS 求最少步数，可对比「代价均一时用 BFS、否则用带剪枝 DFS」
464. 我能赢吗	中等	用整数位集当状态键做记忆化搜索，展示了状态编码与哈希表配合的最小骨架