多米诺和托米诺平铺 图解题解
这道题到底在问什么
- 输入
- n=1
- 输出
- 1(只能竖放一块多米诺)
- 输入
- n=3
- 输出
- 5
- 输入
- n=4
- 输出
- 11
最优解：一步一步想明白
- 3记住这一句:当前 = 前一项×2 + 前第三项,边界 dp[0]=1、dp[1]=1、dp[2]=2。系数 2 与前第三项来自 full/gap 状态消元,下面每一帧都直接套这个递推。
- 4先填好三个边界:空棋盘 dp[0]=1(什么都不放算 1 种)、宽度 1 只能竖一块 dp[1]=1、宽度 2 有「两竖」和「两横」共 dp[2]=2。绿色这三格是递推的起点,后面 0 都会被逐格算出。
- 5推下标 3(棋盘宽 3):紫色 dp[3] 是这一步要算的,它只看两处绿色:紧邻的 dp[2]=2 和往前数第三个 dp[0]=1。
- 6套公式:dp[3] = 2×dp[2] + dp[0] = 2×2 + 1 = 5。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
- 7dp[3] 落格为 5(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
- 8推下标 4(棋盘宽 4):紫色 dp[4] 是这一步要算的,它只看两处绿色:紧邻的 dp[3]=5 和往前数第三个 dp[1]=1。
- 9套公式:dp[4] = 2×dp[3] + dp[1] = 2×5 + 1 = 11。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
- 10dp[4] 落格为 11(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
- 11推下标 5(棋盘宽 5):紫色 dp[5] 是这一步要算的,它只看两处绿色:紧邻的 dp[4]=11 和往前数第三个 dp[2]=2。
- 12套公式:dp[5] = 2×dp[4] + dp[2] = 2×11 + 2 = 24。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
- 13dp[5] 落格为 24(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
- 14推下标 6(棋盘宽 6):紫色 dp[6] 是这一步要算的,它只看两处绿色:紧邻的 dp[5]=24 和往前数第三个 dp[3]=5。
- 15套公式:dp[6] = 2×dp[5] + dp[3] = 2×24 + 5 = 53。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
- 16dp[6] 落格为 53(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
- 17推下标 7(棋盘宽 7):紫色 dp[7] 是这一步要算的,它只看两处绿色:紧邻的 dp[6]=53 和往前数第三个 dp[4]=11。
- 18套公式:dp[7] = 2×dp[6] + dp[4] = 2×53 + 11 = 117。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
- 19dp[7] 落格为 117(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
- 20推下标 8(棋盘宽 8):紫色 dp[8] 是这一步要算的,它只看两处绿色:紧邻的 dp[7]=117 和往前数第三个 dp[5]=24。
- 21套公式:dp[8] = 2×dp[7] + dp[5] = 2×117 + 24 = 258。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
- 22dp[8] 落格为 258(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,到这里 dp[8] 已是最后一格,接着回看整条数组。
- 23推到底:dp[8] = 258,就是 2×8 棋盘的全部铺法数。整条 dp 数组 [1, 1, 2, 5, 11, 24, 53, 117, 258] 一路只靠「前一项×2 + 前第三项」生长出来。
⚠️ 容易写错的地方
✗ 错：忘记每步取模,用 int 直接累乘
✓ 对：每步 % 1e9+7,且 C++/Java 用 long 中间量
取模后单项 dp[i−1] 虽不溢出,但整项 2×dp[i−1]+dp[i−3] 这次加法最大约 3.0e9,超出 32 位 int 上限会得到错误负值;必须边推边取模并用 64 位中间量保存这次加法
✗ 错：把递推记成 dp[i]=dp[i−1]+dp[i−3]
✓ 对：是 2·dp[i−1]+dp[i−3]
前一项要乘 2,漏掉系数会算出比真实值小的结果:比如在 dp[4] 这一步漏掉乘 2,会用 dp[3]+dp[1]=5+1 把正确的 11 算成 6
✗ 错：边界只设 dp[0]、dp[1] 就开始推 i=3
✓ 对：必须先有 dp[0]、dp[1]、dp[2] 三项
递推用到 dp[i−3],i=3 时要读 dp[0],i=2 这项也必须先给定,否则下标读到未初始化的 0
完整代码（Python / C++ / Java）
Python
class Solution:
def numTilings(self, n: int) -> int:
MOD = 10**9 + 7
if n <= 2:
return n
dp = [0] * (n + 1)
dp[0], dp[1], dp[2] = 1, 1, 2
for i in range(3, n + 1):
dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD
return dp[n]C++
#include <vector>
using namespace std;
class Solution {
public:
int numTilings(int n) {
const int MOD = 1000000007;
if (n <= 2) return n;
vector<long long> dp(n + 1);
dp[0] = dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; ++i) dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD;
return dp[n];
}
};Java
import java.util.*;
class Solution {
public int numTilings(int n) {
int MOD = 1_000_000_007;
if (n <= 2) return n;
long[] dp = new long[n + 1];
dp[0] = dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++) dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
return (int) dp[n];
}
}复杂度
时间
O(n)
从 i=3 推到 n 一遍循环,每步常数次乘加与取模
空间
O(n)
用了长度 n+1 的 dp 数组;因只依赖前 1、前 3 项,可压成 3 个滚动变量降到 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 多米诺和托米诺平铺 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
空间能不能从 O(n) 优化到 O(1)?+
可以。dp[i] 只依赖 dp[i−1] 和 dp[i−3],所以最多记住最近三项即可。用三个滚动变量 a、b、c 分别表示 dp[i−3]、dp[i−2]、dp[i−1],每步算出 cur = (2·c + a) % MOD,然后整体左移一位(a←b、b←c、c←cur)。这样空间降到 O(1),时间仍是 O(n),是面试里常被追问的优化点。
这个 2·dp[i−1]+dp[i−3] 的递推是怎么推出来的?+
严谨做法是设两个状态:full[i] 表示「前 i 列完全铺满」的方案数(也就是 dp[i]),gap[i] 表示「前 i 列只差一个角(凸出/凹进一格)」的方案数。分别列出 full 和 gap 的转移并联立消元,把 gap 消掉,就得到只含 full 的封闭式 full[i]=2·full[i−1]+full[i−3]。所以系数 2 与前第三项是消元后的代数结果,不是某一类铺法的直接个数;直接背方程也行,但理解 gap 这个辅助状态能帮你在变体题里自己推。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 多米诺和托米诺平铺 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。