题目描述
思路解析
一句话答案：LeetCode 790 多米诺和托米诺平铺求 2×n 棋盘铺满的方案数：dp[i] 记铺满前 i 列的方案，联立「全铺满/差一角」两状态消元得 dp[i]=2·dp[i-1]+dp[i-3]，每步取模，时间 O(n)、空间可压 O(1)。
一块 2×n 棋盘，多米诺加 L 形托米诺能铺出多少种花样
棋盘是 2 行 n 列。两种砖：2×1 的多米诺，横竖都行；L 形的托米诺，占三格、缺一角。用任意多块不重叠铺满，问有几种铺法，结果对 1e9+7 取模（取模=除以 1e9+7 只留余数，防数字大到存不下；1e9+7 是常用大质数）。n=1 只能竖一块多米诺得 1 种，n=3 有 5 种，n=4 有 11 种。
摆法随 n 指数翻，逐一枚举为什么数不完
把砖一块块摆、摆满就记一种，每往右推一列就分叉一次，铺法数随 n 指数级膨胀，n 一大数不过来；铺到一半的局面在算后面时又被从头重算。把「铺满前 i 列有几种」这个子问题算一次存下来复用，就是动态规划（把「铺满前 i 列」的答案存下来，后面直接取）。
只记「铺满前 i 列」，为什么推着推着会卡住
定义 dp[i] 为铺满 2×i 棋盘的方案数，答案是 dp[n]。可只盯它会卡壳：从左往右铺时两列分界线不总齐平。一块 L 形托米诺会让边界凸出一个角——前面铺满了，第 i 列却只填一格、另一格空着。这种「差一个角」的半满局面 dp[i] 装不下，得再补一个状态 gap[i]：前 i 列铺满、只在末列凸出一角的方案数。
补上「差一个角」的状态，递推怎么就成了 2·前一项加前第三项
给两个状态各列转移。铺满第 i 列有三条收尾方式：dp[i-1] 右边竖插一块多米诺、dp[i-2] 右边平放两块横多米诺、或拿托米诺补一个带角的 gap 局面（gap 有两种镜像方向，凑出系数 2）。
把两条式子联立、代入消去 gap（联立=把两条式子摆一起，消元=用代入法把 gap 约掉，只剩 dp），留下只含 dp 的递推 dp[i]=2·dp[i-1]+dp[i-3]。要紧的是：系数 2 和「前第三项」是消元后的代数结果，不对应具体铺法，别硬找图形对应。gap 这个辅助状态是这题的枢纽，少了它下面的消元根本联立不起来。
拿 n=3、n=4 亲手把 dp 推出 5 和 11
先摆好三个边界：dp[0]=1（空棋盘算一种）、dp[1]=1（宽 1 只能竖一块）、dp[2]=2（宽 2 有两竖和两横）。递推要读 dp[i-3]，起手须凑齐前三项。套 dp[i]=2·dp[i-1]+dp[i-3]：dp[3]=2×dp[2]+dp[0]=2×2+1=5，对上题面 n=3；dp[4]=2×dp[3]+dp[1]=2×5+1=11，对上 n=4。逐格推到 dp[8]，整条数组是 1、1、2、5、11、24、53、117、258。
漏掉系数 2，dp[4] 为什么会算成 6
从第 3 项推到第 n 项一趟线性循环，每步几次乘加取模，时间 O(n)；数组长 n+1，空间 O(n)，回看前一项和前第三项即可，压成三个滚动变量降到 O(1)。
漏系数 2 最常见，写成 dp[i]=dp[i-1]+dp[i-3]，dp[4] 会算成 6 而不是 11。取模也别忘——2×dp[i-1]+dp[i-3] 一次加法就能顶破 32 位翻成负数，C++/Java 得用 64 位、每步取模。边界还得铺满前三项：第 3 项要读 dp[0] 又得先有 dp[2]，只铺 dp[0]、dp[1] 就开推会读到没初始化的 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句:当前 = 前一项×2 + 前第三项,边界 dp[0]=1、dp[1]=1、dp[2]=2。系数 2 与前第三项来自 full/gap 状态消元,下面每一帧都直接套这个递推。
先填好三个边界:空棋盘 dp[0]=1(什么都不放算 1 种)、宽度 1 只能竖一块 dp[1]=1、宽度 2 有「两竖」和「两横」共 dp[2]=2。绿色这三格是递推的起点,后面 0 都会被逐格算出。
推下标 3(棋盘宽 3):紫色 dp[3] 是这一步要算的,它只看两处绿色:紧邻的 dp[2]=2 和往前数第三个 dp[0]=1。
套公式:dp[3] = 2×dp[2] + dp[0] = 2×2 + 1 = 5。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
dp[3] 落格为 5(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
推下标 4(棋盘宽 4):紫色 dp[4] 是这一步要算的,它只看两处绿色:紧邻的 dp[3]=5 和往前数第三个 dp[1]=1。
套公式:dp[4] = 2×dp[3] + dp[1] = 2×5 + 1 = 11。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
dp[4] 落格为 11(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
推下标 5(棋盘宽 5):紫色 dp[5] 是这一步要算的,它只看两处绿色:紧邻的 dp[4]=11 和往前数第三个 dp[2]=2。
套公式:dp[5] = 2×dp[4] + dp[2] = 2×11 + 2 = 24。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
dp[5] 落格为 24(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
推下标 6(棋盘宽 6):紫色 dp[6] 是这一步要算的,它只看两处绿色:紧邻的 dp[5]=24 和往前数第三个 dp[3]=5。
套公式:dp[6] = 2×dp[5] + dp[3] = 2×24 + 5 = 53。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
dp[6] 落格为 53(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
推下标 7(棋盘宽 7):紫色 dp[7] 是这一步要算的,它只看两处绿色:紧邻的 dp[6]=53 和往前数第三个 dp[4]=11。
套公式:dp[7] = 2×dp[6] + dp[4] = 2×53 + 11 = 117。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
dp[7] 落格为 117(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,接着推下一格。
推下标 8(棋盘宽 8):紫色 dp[8] 是这一步要算的,它只看两处绿色:紧邻的 dp[7]=117 和往前数第三个 dp[5]=24。
套公式:dp[8] = 2×dp[7] + dp[5] = 2×117 + 24 = 258。系数 2 与前第三项是 full/gap 状态消元后的结果,这里直接用已消元的递推算值。
dp[8] 落格为 258(这里数不大不触发取模,n 大时每步都要 % 1e9+7 防溢出)。蓝色是已算好的前缀,到这里 dp[8] 已是最后一格,接着回看整条数组。
推到底:dp[8] = 258,就是 2×8 棋盘的全部铺法数。整条 dp 数组 [1, 1, 2, 5, 11, 24, 53, 117, 258] 一路只靠「前一项×2 + 前第三项」生长出来。
边界:n=1 得 1、n=2 得 2、n=3 起进入递推得 5。
两个延伸:三变量滚动压成 O(1);辅助状态消元可严谨推出方程。
参考代码
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]复杂度
- 时间：O(n)，从 i=3 推到 n 一遍循环,每步常数次乘加与取模
- 空间：O(n)，用了长度 n+1 的 dp 数组;因只依赖前 1、前 3 项,可压成 3 个滚动变量降到 O(1)
易错点
面试追问把动画讲成自己的话
追问空间能不能从 O(n) 优化到 O(1)?
追问这个 2·dp[i−1]+dp[i−3] 的递推是怎么推出来的?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
香槟塔
LeetCode 799 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题