剑指 Offer 动态规划系列：矩形覆盖——用 n 个 2×1 小矩形铺满 2×n 大矩形的递推推导与 O(1) 空间解法（CS-Notes）

本篇基于 CS-Notes 剑指 Offer 题解中的 10.2 矩形覆盖 展开，讲解如何用 n 个 2×1 的小矩形无重叠地覆盖一个 2×n 的大矩形、总共有多少种方法。读完本文，你将掌握"枚举最后一步放法"这一建模套路、递推公式的严格推导过程，以及从朴素递归到滚动变量、时间 O(n) 空间 O(1) 的完整优化路径，并能把它与斐波那契数列、跳台阶等同族问题融会贯通。

题目描述

我们可以用 2×1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2×1 的小矩形无重叠地覆盖一个 2×n 的大矩形，总共有多少种方法？

即：大矩形的尺寸固定为 2 行 n 列，恰好要放入 n 个 2×1 的"骨牌"（每个骨牌可横放占 1×2，也可竖放占 2×1），要求恰好铺满且不重叠，问铺法总数。

从特例入手：确定递推的边界条件

做铺放类计数题，最稳妥的办法是先手写小规模的解，再找规律。

当 n = 1 时，2×1 的大矩形只能用 1 个小矩形竖着铺，只有 1 种方法：f(1) = 1。

当 n = 2 时，有两种覆盖方法：要么两个小矩形都竖着放，要么都横着放：f(2) = 2。

上图为 n = 2 时的全部两种铺法。这两个值就是后续递推的初始条件。

递推公式的推导：只关心最左边一列的放法

要覆盖 2×n 的大矩形，可以只看最左边 2 列区域的铺法，它只有两种可能：

1. 在左上角竖着放一个 2×1 小矩形：它独自占据第 1 列，剩下的部分是一个 2×(n−1) 的矩形，铺法数为 f(n−1)；
2. 在左上角横着放一个 2×1 小矩形：它占据第 1、2 列的上半格，此时为了铺满第 1、2 列的下半格，左上角下方必须再横着放一个 2×1 小矩形（这是唯一可行的补法）。也就是说"左上角横放"必然成对出现，它独占前 2 列，剩下的部分是一个 2×(n−2) 的矩形，铺法数为 f(n−2)。

两种情况互斥且穷尽了左上角的所有放法，因此得到原 10.2 矩形覆盖 中给出的递推公式：

即：

• f(1) = 1
• f(2) = 2
• f(n) = f(n−1) + f(n−2)，n > 2

按此递推，前几项为 f(1)=1、f(2)=2、f(3)=3、f(4)=5、f(5)=8……可以看出 f(n) 恰好是斐波那契数列整体右移一位，即 f(n) = Fib(n+1)（若约定 Fib(1)=1、Fib(2)=1）。这与仓库中 10.1 斐波那契数列 是同一族递推，只是初始条件不同。

解法一：朴素递归（反面教材）

直接按递推式写递归：

public int rectCover(int n) {
    if (n <= 1)
        return 1;
    if (n == 2)
        return 2;
    return rectCover(n - 1) + rectCover(n - 2);
}

问题在于递归会重复求解大量子问题：rectCover(n−1) 与 rectCover(n−2) 都会各自调用 rectCover(n−2)，以此类推，时间复杂度高达指数级的 O(2^n)，n 稍大就会超时。这也正是 10.1 斐波那契数列 一文中强调的"递归重复计算子问题"的缺陷，动态规划的核心就是缓存子问题的解来消除这种重复。

解法二：自底向上动态规划，O(N) 空间

用数组把子问题的解缓存起来，自底向上填表即可：

public int rectCover(int n) {
    if (n <= 2)
        return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

时间复杂度 O(n)，空间复杂度 O(n)。这与 10.1 斐波那契数列 中的 DP 数组版本结构完全一致。

解法三：滚动变量优化，O(1) 空间（仓库官方解法）

考虑到计算第 i 项只依赖第 i−1 项和第 i−2 项，无需保留整张 dp 表，用两个变量滚动更新前两项的值即可，从而把空间复杂度由 O(n) 降为 O(1)。这正是 10.2 矩形覆盖 给出的官方解法：

public int rectCover(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int result = 0;
    for (int i = 3; i <= n; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}

逐行解析：

代码	作用
if (n <= 2) return n;	处理边界：f(1)=1、f(2)=2，直接返回
int pre2 = 1, pre1 = 2;	初始化前两项 f(1)=1、f(2)=2
result = pre2 + pre1;	计算 f(i) = f(i−2) + f(i−1)
pre2 = pre1; pre1 = result;	窗口整体右移一位，为下一轮做准备

时间复杂度 O(n)，空间复杂度 O(1)。可以验证：n=3 时循环执行一次，result = 1 + 2 = 3，与手算 f(3)=3 一致；n=4 时 result = 2 + 3 = 5，与 f(4)=5 一致。

同类问题对照：一个递推，三种题型

仓库把矩形覆盖归入剑指 Offer 的"动态规划"分类（见 剑指 Offer 题解 - 目录 中"动态规划"小节）。围绕同一个递推框架 f(n) = f(n−1) + f(n−2)，本章还有两道变体值得对照学习：

• 10.1 斐波那契数列：直接求 Fib(n)，初始条件为 f(0)=0、f(1)=1；同样的"数组版 → 滚动变量版"两级优化在这里也有完整演示；
• 10.3 跳台阶：青蛙一次跳 1 级或 2 级，其递推式与矩形覆盖完全相同（f(n) = f(n−1) + f(n−2)，f(1)=1、f(2)=2），本质等价：把"最后一级台阶的跳法"对应到"最左边一列的铺法"即可；
• 10.4 变态跳台阶：青蛙可以跳 1~n 级，递推退化为 f(n) = 2·f(n−1) 的等比数列，是本章对"枚举最后一步"思路的进一步抽象。

可以这样记忆：矩形覆盖和跳台阶是同一递推的两个物理模型；面试时先写清边界条件 f(1)、f(2)，再说明"最后一步只有两种选择"，即可快速推出递推式。

常见追问与扩展

追问 1：n 很大时会不会溢出？ 解法三返回 int，而 f(n) 按斐波那契速度增长，当 n 较大时会超出 int 范围。若题目给定 n 的上限，先估算 Fib(n+1) 的量级，必要时改用 long 或取模后的答案（例如输出对 10^9+7 取模的结果），以具体题目约束为准。

追问 2：如果把小矩形换成 3×1，还有多少种铺法？ 这是同一思路的自然推广。此时最左边一列的放法有三种：竖着放 1 个 3×1；或横着放 2 个（上下各一，独占前两列，且此时前两列必须都横放，故成组计数）；逐一枚举可得递推 f(n) = f(n−1) + 2·f(n−2)（f(1)=1、f(2)=3）。解法仍是填表 + 滚动变量，只是系数从 1 变成 2，建模方法完全一致。

追问 3：能不能直接给出闭式解？ 由于 f(n) = Fib(n+1)，理论上可以套用斐波那契通项公式，但面试场景下递推 + 滚动变量的 O(n)/O(1) 解法既简单又稳健，是最标准的答案。

小结

矩形覆盖题的解题路径可以归纳为三步：

1. 枚举最后一步：只看最左边一列，铺法被穷尽为"竖放 1 块"和"横放 2 块"两种，得到 f(n) = f(n−1) + f(n−2)；
2. 定边界：f(1) = 1、f(2) = 2；
3. 选实现：朴素递归（指数级，仅作反面教材）→ DP 数组（O(n) 空间）→ 滚动变量（O(1) 空间，推荐）。

掌握这一范式后，10.1 斐波那契数列、10.3 跳台阶、10.4 变态跳台阶 乃至更多"枚举最后一步"的计数题都能按同一套路快速求解。