剑指 Offer No10 矩阵覆盖:用 2×1 小矩形无重叠覆盖 2×n 大矩形的斐波那契数列解法
剑指 Offer No10 矩阵覆盖:用 2×1 小矩形无重叠覆盖 2×n 大矩形的斐波那契数列解法
导读
本文基于《InterviewGuide》开源仓库「带你快速刷完 67 道剑指 offer」专栏的第 10 题(10-剑指offer.md),完整讲解「矩阵覆盖」这一经典递推问题的思路推导与 C++ 实现。题目要求用 n 个 2×1 的小矩形横放或竖放,无重叠地覆盖一个 2×n 的大矩形,求总共有多少种覆盖方法。读完本文你将掌握:如何把几何覆盖问题转化为斐波那契数列递推、递归解法的正确写法与性能短板、滚动变量循环解法的原理,以及「二刷」版代码为什么是面试中最稳妥的提交形态。
本题对应牛客网《剑指 Offer》专题原题,属于校招、社招面试中高频出现的「斐波那契数列变种」家族题,与本专栏的 No7 斐波那契数列、No8 跳台阶、No9 变态跳台阶 同源同构,是入门动态规划(递推 + 滚动变量)最典型的训练题之一。
一、题目描述
我们可以用 2×1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2×1 的小矩形无重叠地覆盖一个 2×n 的大矩形,总共有多少种方法?
题目约束与边界条件(由题面与仓库解法共同确认):
| 参数 | 说明 |
|---|---|
| 小矩形尺寸 | 2×1,可横放(占 2 列 × 1 行)或竖放(占 1 列 × 2 行) |
| 大矩形尺寸 | 2×n,即宽度恒为 2、长度为 n |
| 小矩形数量 | n 个(恰好铺满 2×n 的面积:2n ÷ 2 = n) |
| 覆盖要求 | 无重叠、无遗漏,恰好完全覆盖 |
| 返回结果 | 覆盖方法总数 |
题目给出的示例:当 n=3 时,2×3 的大矩形共有 3 种覆盖方法:
- 三个 2×1 小矩形全部竖放,依次排满 3 列;
- 左侧两个横放(占满前 2 列)、右侧一个竖放;
- 左侧一个竖放、右侧两个横放(占满后 2 列)。
原文档为这三张覆盖示意图引用了 http://oss.interviewguide.cn/img/202205072310734.png,该图片为仓库外资源、当前仓库内不存在对应文件,因此这里用文字与表格还原,不影响理解。
二、核心思路:把覆盖问题改写成斐波那契递推
1、画图找规律:从最后一步出发做状态分解
覆盖 2×n 大矩形时,考察最左边(或最右边)一列是如何被覆盖的,只有两种可能:
- 竖放一个小矩形:2×1 的矩形竖着恰好占满最左侧 1 列。剩下的部分是一个 2×(n−1) 的大矩形,覆盖方法数为 f(n−1);
- 横放两个小矩形:横放需要两个 2×1 矩形上下拼起来,才能占满最左侧 2 列。剩下的部分是一个 2×(n−2) 的大矩形,覆盖方法数为 f(n−2)。
因此覆盖方法总数满足:
f(n) = f(n-1) + f(n-2)
这正是斐波那契数列的递推式。结合边界:
- n = 0:没有矩形可覆盖,方法数为 0(仓库解法统一按
number <= 2直接返回 number 处理); - n = 1:只有 1 个 2×1 小矩形,只能竖放,f(1) = 1;
- n = 2:可以两个竖放,也可以两个横放拼成 2×2,f(2) = 2。
于是整体序列为 f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8, …,与斐波那契数列错位对齐(f(0)=0、f(1)=1 的斐波那契数列从第 3 项起与本题一致)。原作者在「二刷」小结中也直接点明了这一点:「感觉还是斐波那契数列的变种」。
2、与同专栏递推题的对照
把本题与本专栏前面几题放在一起,能更清楚地看到这一族题目的递推骨架(均可在仓库对应文档中验证):
| 题目 | 递推式 | 边界 | 仓库文档 |
|---|---|---|---|
| 斐波那契数列 | f(n) = f(n−1) + f(n−2) | f(0)=0, f(1)=1 | 07-剑指offer.md |
| 跳台阶(青蛙跳 1 或 2 级) | f(n) = f(n−1) + f(n−2) | f(1)=1, f(2)=2 | 08-剑指offer.md |
| 变态跳台阶(可跳 1~n 级) | f(n) = 2·f(n−1) | f(1)=1 | 09-剑指offer.md |
| 矩阵覆盖(本题) | f(n) = f(n−1) + f(n−2) | f(1)=1, f(2)=2 | 10-剑指offer.md |
可以看到,矩阵覆盖与「跳台阶(只能跳 1 或 2 级)」在递推式和边界上完全同构:f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2)。对应的 LeetCode 题目即 70. 爬楼梯(力扣原题在仓库中同样收录于动态规划分类)。这类「把一个规模为 n 的问题,按第一步/最后一步的选择拆成两个子问题」的建模方式,是动态规划入门阶段必须掌握的思维。
三、解法一:递归,画画图就能写出来(思路最直观)
原作者给出的第一种写法,直接照搬递推式:
int rectCover(int number) {
if (number <= 2) return number;
return rectCover(number - 1) + rectCover(number - 2);
}
要点分析:
- 边界处理:
number <= 2时直接返回 number,覆盖了 n=0、n=1、n=2 三种情况,与递推边界一致; - 正确性:递归树完全等价于 f(n) = f(n−1) + f(n−2),小数据量(如题目常规范围)下结果必然正确;
- 性能短板:这是典型的「自顶向下、无记忆化」递归。计算 f(n) 需要重复计算大量子树(f(n−2) 会被 f(n) 与 f(n−1) 各算一遍,指数级膨胀),当 n 稍大时函数调用次数呈斐波那契量级增长,运行缓慢,还可能因递归深度过大触发栈溢出。原作者在 No8 跳台阶 中对该写法给出的评价是「递归做法,真的很耗时」,在 No7 斐波那契数列 中则标注为「递归,慢得多」——同一判断同样适用于本题。
因此递归版只适合用来验证思路,不适合作为面试最终提交。
四、解法二:循环 + 滚动变量(推荐,时间 O(n) 空间 O(1))
原作者给出的第二种写法用「三个变量滚动前进」的方式消除重复计算:
int rectCover(int number) {
if (number <= 2) {
return number;
}
int first = 1, second = 2, third = 3;
for (int i = 3; i <= number; ++i) {
third = first + second;
first = second;
second = third;
}
return third;
}
执行过程逐行拆解:
- 先处理边界:
number <= 2直接返回 number; - 初始化三个变量:
first = f(1) = 1、second = f(2) = 2、third先赋 3(初值其实无关紧要,进入循环后立即被覆盖); - 循环从 i = 3 到 number,每轮先计算
third = first + second,即 f(i) = f(i−2) + f(i−1),再整体右移first = second; second = third; - 循环结束后
third即 f(number),返回即可。
滚动变量的本质是只用三个 int 就完成了整条斐波那契序列的迭代:
| 循环轮次 i | 计算前 (first, second) | third = first + second | 计算后 (first, second) |
|---|---|---|---|
| 3 | (1, 2) | 3 | (2, 3) |
| 4 | (2, 3) | 5 | (3, 5) |
| 5 | (3, 5) | 8 | (5, 8) |
| n | (f(n−2), f(n−1)) | f(n) | (f(n−1), f(n)) |
复杂度:时间 O(n)(单层循环),空间 O(1)(只占用 3 个整型变量)。相比递归版的指数级时间,这是数量级的提升,也是面试中应当给出的主流答案。
五、二刷版:边界收拢 + 循环提速的最终形态
原文档还记录了阿秀「二刷」时重新整理的一版代码,并附有当时的实测数据(运行时间 3ms、占用内存 464k,数据来源:10-剑指offer.md):
int rectCover(int number) {
if (number <= 2) return number;
int first = 1, second = 2, third = 0;
for (int i = 3; i <= number; ++i) {
third = first + second;
first = second;
second = third;
}
return third;
}
与解法二的差异仅有两处,都属于代码风格与鲁棒性的微调:
third初始化为 0 而不是 3:避免在 number < 3 却误入循环(或循环被跳过)时返回未定义初值,语义更严谨;- 边界条件合并为一行
if (number <= 2) return number;:与递归版保持一致的判断口径,n=0/1/2 三种情况一次收拢。
如果 number 恰好等于 3,循环只执行一轮:third = 1 + 2 = 3,正确;如果 number 等于 2,直接命中边界返回 2,不会进入循环。可见 third = 0 的初始化只是防御性写法,实际从 i=3 开始循环时它总会在第一轮被赋值。
二刷版的这个写法与本专栏其他题目(No7、No8)的「二刷」代码结构完全一致:first/second/third 三变量 + for 循环滚动,属于阿秀本人验证过的、可以直接照抄进面试环境的稳定模板。
六、变体与扩展:n 很大时怎么办(延伸思考)
虽然牛客剑指 offer 原题的数据范围用 int 循环即可通过,但把「矩阵覆盖」放入更通用的动态规划语境,可以延伸出两个面试加分点:
1、数组化 DP(便于扩展与回溯)
当题目后续要求输出覆盖方案本身而非只计数时,滚动变量无法保留中间状态,可改用数组:
// 以 vector 保存 f(1)..f(n),空间换能力
int rectCover(int number) {
if (number <= 2) return number;
std::vector<int> dp(number + 1, 0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= number; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[number];
}
这与仓库 No7 斐波那契数列 中「采用三个元素保存数组即可」的 F[i % 3] 滚动数组思路同源,都是「在 O(n) 空间里做递推」的形态。
2、大数溢出
当 n 超过约 40 时,f(n) 会超过 32 位 int 的表示范围(2^31−1)。若题目把 n 的上限放大,返回值需要改为 long long 或采用取模(如对 1e9+7 取模)的方式,这一点在面试追问「n 很大怎么办」时是必答项。
七、小结与速记卡片
| 维度 | 结论 |
|---|---|
| 题目本质 | 斐波那契数列变种:f(n) = f(n−1) + f(n−2),f(1)=1, f(2)=2 |
| 建模方法 | 考察最左列:竖放 → 剩 2×(n−1);两个横放 → 剩 2×(n−2) |
| 递归版 | 代码最短、思路最直,但指数级重复计算,只宜验思路 |
| 循环版 | 三变量滚动,时间 O(n)、空间 O(1),面试首选 |
| 二刷版 | third 初始化为 0 + 边界合并,鲁棒性更好的最终形态 |
| 同源题目 | No7 斐波那契数列、No8 跳台阶、No9 变态跳台阶、LeetCode 70. 爬楼梯 |
面试现场建议按「先画图讲清两种拆分 → 给出 f(n)=f(n−1)+f(n−2) → 直接写滚动变量循环版」的顺序作答,并用 n=3 得 3、n=4 得 5 快速手算验证,即可稳拿这题。