1. 先从一个看起来非常简单的2×n开始第一次接触骨牌问题的人通常都会觉得它不就是个斐波那契数列吗确实2×n的情况简单到可以用一行递推式写完但它恰恰是理解后面所有复杂情况的地基。这个“简单”里藏着一个很重要的思维方式——怎么把一个铺砖问题抽象成状态转移。问题描述很直白有一个2行n列的矩形棋盘用若干个1×2和2×1的骨牌把它铺满问一共有多少种不同的铺法。这里的骨牌不能旋转出第三种形态只有横着放和竖着放两种摆法。我最早刷这道题的时候第一反应是去枚举排列然后很快发现n稍微大一点就炸了。后来才意识到这类问题本质上是一个动态规划思考方式是看最后一列是怎么被覆盖的。设dp[i]表示铺满前i列的总方案数。看第i列它有3种可能的覆盖方式第i列放一块竖着的2×1骨牌这时候前i-1列是完整的方案数是dp[i-1]第i列和第i-1列各放一块横着的1×2骨牌两块骨牌分别占据第i-1列和第i列的上、下两行。这时候前i-2列是完整的方案数是dp[i-2]。于是得到dp[i] dp[i-1] dp[i-2]边界条件dp[0] 1表示空棋盘算一种铺法dp[1] 1最终dp[n]就是答案。计算一下n1是1种n2是2种n3是3种n4是5种n5是8种——妥妥的斐波那契数列。这个推导看起来太简单了但请记住这里的核心思路把问题拆成“最后一列的状态”和“前面部分的状态”两部分。后面3×n和n×m的所有复杂度都是因为“最后一列/最后一个格子的状态”变得不那么直观了但思考路径是一脉相承的。如果你直接跳过了2×n去啃大规模的情况大概率会被状态设计绕晕所以建议先把这段彻底吃透。2. 3×n的真正难点为什么不能直接套用斐波那契3×n的骨牌问题在经典dp题单里出现频率极高也是面试官特别爱用来考察候选人对状态设计理解深度的一道题。如果拿着2×n的思路硬套会觉得“最后一列无非就是竖着放一块3×1”但事实上根本不存在3×1这种骨牌。骨牌只有两种尺寸1×2和2×1所以3×n的每一列高度是3无法用一整块竖骨牌覆盖。这就是3×n和2×n之间最根本的区别。2×n里有“竖着放一块”这个简单选项到了3×n竖着放只能覆盖2格剩下1格必须和邻列配合。所以状态设计必须从“这一列是否完整”扩展到“这一列的每个格子被覆盖到了什么程度”。2.1 状态压缩的引入三位二进制我们用一个3位的二进制数来表示某一列每个格子的覆盖状态。每一位对应这一列的一行0表示这一格还没被覆盖1表示这一格已经被骨牌覆盖了。回想一下最后一块骨牌带来的影响覆盖当前列某个格子的骨牌可能来自左边一列伸过来的横骨牌也可能来自当前列内部竖着放的骨牌还可能当前格子是横骨牌的一部分伸向了右边一列。这个过程如果不用状态位去记录“谁被谁占了”后面的转移根本没法写。定义dp[i][state]表示前i列全部铺满且第i1列受到“从左往右伸出来的横骨牌”影响后的状态为state时的方案数。这里的state是一个3位二进制数bit为1表示对应的行被来自左边的一个横骨牌占据了。换句话说处理完前i列之后第i1列上已经有某些格子被占掉了这些格子不能再放新骨牌。初始时dp[0][0] 1也就是还没开始铺第1列没有被任何伸出的骨牌占据。目标是dp[n][0]即铺完前n列且没有骨牌伸到n1列去。2.2 转移规则四种放置动作从dp[i][state]转移到dp[i1][next_state]我们要在第i1列上填补那些state中为0的位置并决定是否往第i2列伸出新的横骨牌。具体有4种动作竖放在第i1列中某个高度为2的连续空格区域放一块2×1骨牌。这个动作只影响当前列的两个位置把它们从0变成1不会影响第i2列。横放右伸在第i1列中某个空格位置放一块1×2骨牌骨牌横跨第i1列和第i2列的同一行。这个动作把当前列的该位置从0变成1同时把第i2列同一行的位置置为1。跳过填空如果state中第k位已经是1说明该位置被来自左边的横骨牌覆盖了无需处理。当前列填满后剩余state中为0的位置若无法通过上述动作覆盖则此转移非法。用一个具体例子来感受。假设当前state 001表示第i1列最下面一行已经被左边的横骨牌占了。那么第i1列还剩下上面两行是空的上面两行是连续的2格可以竖着放一块2×1把这两个格子填掉。此时第i1列全部为1且没有往第i2列伸出的部分所以next_state 000。也可以在上面两行分别横放骨牌往第i2列伸出两块横骨牌此时next_state 011第i2列的第1、2行被占。注意这里两块横骨牌必须同时出现因为上面两行的空格是两个相邻但各自独立的行位如果只放一块横骨牌另一行就没法覆盖了。再比如state 010表示中间行被占剩下第1行和第3行两个空格。这两个空格是不连续的无法竖放一块2×1。唯一的办法是第1行和第3行分别横放向右伸到第i2列所以next_state 101。如果state 011只剩第1行空格只能横放一块next_state 100。这个逻辑写成代码可以直接用DFS对每一列做填充枚举也可以在预处理阶段枚举所有state和next_state的合法转移对。后者更快因为3位的二进制数一共只有8个状态转移对最多也就8×864个直接打表。2.3 从状态转移到矩阵快速幂当n比较小的时候直接for i从1到n做dp[i1][next_state] dp[i][state]就行复杂度O(n×状态数×转移数)n到1e5以内都没压力。但如果n到了1e12呢3×n问题里n可以做乘法这时候就要用到矩阵快速幂。把dp[i]看成8维向量转移关系写成8×8的矩阵M其中M[state][next_state]表示从state转移到next_state的方案数。那么dp[i1] M × dp[i]于是dp[n] M^n × dp[0]。矩阵快速幂的复杂度是O(8^3 log n)非常快。我实际测试的时候构建转移矩阵有个小陷阱state和next_state谁是行谁是列容易搞反。这里建议统一成矩阵M[state][next_state]乘的时候是dp[i1][next_state] sum(M[state][next_state] × dp[i][state])。如果写反了查错会查到怀疑人生。我在本地调试时打印过一个小n的dp数组和矩阵快速幂的结果做对比确认无误之后才敢提交。2.4 3×n的递推式一个更优雅的写法如果你只是想知道3×n的答案其实还有个更简洁的递推公式。设f[i]表示3×n铺满的方案数g[i]表示3×n铺满且多出来一个角也就是有一行比另外两行多一列的方案数可以得到f[i] f[i-1] 2 × g[i-1] g[i] f[i-2] g[i-1]解释一下这两行的含义。f[i]的最后状态有两种可能一种是最左边一列直接竖放三块2×1不对刚说了没有3×1但这里不是竖放三块2×1让我重新理一下——事实上3×n的铺法中最后一列的覆盖方式需要更仔细地分类这个递推式的推导过程比较容易写错所以我更推荐直接用状态压缩矩阵快速幂的通用解法它天然不会漏情况。n2时答案是3n3时答案是0n4时答案是11。这个“n为奇数时为0”的结论可以用一個很简单的染色论证把棋盘黑白相间染色每块骨牌总是覆盖一黑一白所以两色格子数必须相等。3×n棋盘黑白格子数量在n为奇数时不相等所以答案是0。这种基于染色法的奇偶性判断在做n×m判断时也经常用到。3. n×m复杂棋盘下的轮廓线dp如果你以为3×n就是终点了那n×m会把你拉回现实。当行数和列数都不固定时没法再用“这一列”作为状态的基本单元因为列的状态长度取决于行数而行数本身也不固定。这里需要用到的经典方案是轮廓线dp也叫插头dp的入门形态。3.1 什么是轮廓线想象你拿着一个刷子从左到右、从上到下一格一格地扫描棋盘。任何时候“已经处理过的格子”和“还没处理的格子”之间都有一条边界线这条线就是轮廓线。轮廓线dp的核心思想就是只记录这条轮廓线上的状态而不是整个棋盘的状态。具体来说当扫描到第i行第j列时轮廓线是从上一行穿过来的m个位置确切地说是上一行对应的那一排格子是否被覆盖再加上当前行已经扫描过的格子状态。由于m可能很大直接用bool数组做记忆化会爆空间所以需要状态压缩。假设列数为m我们用一个m位的二进制数来表示轮廓线上每个位置的状态。这个二进制数的第k位表示当前正在扫描的格子所在行的第k列是否已经被某个从左/上伸过来的骨牌覆盖。处理过程中这个状态被不断更新就像滚动的传送带一样。3.2 状态设计与转移细节从左上角开始扫描设当前扫描到格子(i, j)。我们用state表示轮廓线状态这个state的二进制位从低到高分别对应第1列到第m列方便起见也可以反过来只要转移一致就行。对于当前格子(i, j)它只有四种可能被覆盖的方式已经被来自上方的骨牌覆盖也就是说state中对应j这一位是1此时不能放新骨牌直接跳到下一个格子同时把当前行的这一位变成0表示这个格子已经处理完不再对后续有影响。被来自左侧的骨牌覆盖这个信息体现在上一格处理完后的state更新中。实现时通常在转移时判断左格是否被横骨牌覆盖。放一块竖着的2×1骨牌要求当前格子为空、下一行的同一列也是空的在n×m的边界内。放完后轮廓线上这一位变成1表示下方格子被覆盖了。放一块横着的1×2骨牌要求当前格子为空、右边的格子也是空的在列边界内。放完后轮廓线上这个位置和下一个位置都变成1。这个过程里最容易出错的就是“当前格子已经被覆盖时轮廓线对应位要变成0”这一步。如果漏写状态会越滚越乱。3.3 轮廓线dp代码模板我习惯用递推的形式写轮廓线dp用一个二维的滚动dp数组其中一维是状态另一维是“当前扫到哪个格子”的奇偶标记。模板如下const int MAXM 10; long long dp[2][1 MAXM]; long long solve(int n, int m) { if ((n * m) % 2 1) return 0; // 面积是奇数时不可能铺满 memset(dp, 0, sizeof(dp)); int cur 0; dp[cur][0] 1; for (int i 0; i n; i) { for (int j 0; j m; j) { cur ^ 1; memset(dp[cur], 0, sizeof(dp[cur])); for (int state 0; state (1 m); state) { if (dp[cur ^ 1][state] 0) continue; // 当前格是否已被上方覆盖 if ((state j) 1) { // 已被覆盖跳过并将该位清零 int ns state ~(1 j); dp[cur][ns] dp[cur ^ 1][state]; } else { // 未被覆盖尝试放横骨牌 if (j 1 m !((state (j 1)) 1)) { int ns state | (1 j) | (1 (j 1)); ns ~(1 j); // 当前格子处理完不再占轮廓线 // 注意这里需要仔细处理实际上横放后当前格子和右格都会被标记但当前格在下一轮会作为历史需要清掉 dp[cur][ns] dp[cur ^ 1][state]; } // 尝试放竖骨牌 if (i 1 n) { int ns state | (1 j); dp[cur][ns] dp[cur ^ 1][state]; } } } } } return dp[cur][0]; }注意上面这段代码为了展示细节横放部分的状态更新写得很别扭实际写的时候我会把“当前格处理完毕后轮廓线上当前位自动失效”这件事统一处理。更清晰的做法是转移时先把state中第j位清零再根据需要把第j位竖放或第j1位横放置1。因为当前格一旦扫过它就不再属于轮廓线只有它伸出去影响后面的部分才需要保留。如果直接按上面的实现跑你会发现n2、m3的输出是3n3、m3的输出是0和理论值是一致的。这里强调一下轮廓线dp的状态数是指数级的2^m所以m一般不能超过10到12否则需要改成插头dp或使用更高阶的优化不过那就是另一个话题了。3.4 如何验证自己的dp没写错写这类dp最怕不是不会转移而是转移里有一两个case漏了答案差一点你自己还发现不了。我的建议是先用暴力搜索DFS回溯算小棋盘的结果和dp结果对拍。棋盘大小从1×1开始逐行逐列扩大对到3×4以上基本就可以确信dp写对了。暴力方法也很直接找棋盘上第一个没被覆盖的格子尝试放横骨牌或竖骨牌递归继续最后统计完整铺满的路径数。这个暴力的复杂度极高但用来验证dp绰绰有余。我放一个参考数值表方便你自检棋盘铺法数2×222×332×453×233×4114×4364×4是36这个数字我印象很深因为曾经有个同学用轮廓线dp写出了72还振振有词地说“对称性应该乘2”后来排查发现是他在处理每个格子时没有区分“当前格已被覆盖”的情况导致同一铺法被重复计数了。4. 从2×n到3×n再到n×m这条递进路线到底在练什么很多初学者会觉得既然有了n×m的轮廓线dp为什么还要学2×n和3×n直接上终极版不就行了这种想法其实忽略了dp学习最重要的一点每一种问题规模都代表了一种状态设计的层次。2×n告诉你“最后一列”可以作为独立状态3×n告诉你当列结构变复杂时需要用状态压缩来表达“局部未完成”的信息n×m则彻底抛弃了“列”的概念改用轮廓线记录扫描边界。这三者不是相互替代的关系而是同一个问题在不同约束下的演化。我记得第一次完整推导3×n的状态转移时花了将近一个晚上但第二天做n×m的轮廓线dp时思路顺畅得惊人。因为3×n里已经用到了“当前列的某些格子被伸过来的骨牌占据”这种思想而轮廓线dp就是把这个思想推广到每一行每一列。这条递进路线本质上是在训练一种能力面对一个复杂约束系统如何选出最小的状态集合使得未来决策不受历史细节的干扰。如果你在面试中被问到骨牌问题我建议先问清楚棋盘规模。n小m大还是n大m小如果是n和m都很大那就要考虑有没有特殊的数学规律如果有一维特别小状态压缩是最稳的方案如果两个维度都不大直接轮廓线dp或者插头dp都能搞定。根据规模选算法是这题在面试里真正的考点。4.1 空间优化滚动数组的边界处理n×m的轮廓线dp中由于每一轮只依赖上一格的状态可以用一个2×2^m的滚动数组。但有一个小坑换行的时候轮廓线的含义会发生变化。当从第i行的最后一列跳到第i1行的第一列时state的每一位含义整体右移/左移了一格取决于你的状态压缩顺序。比如你在处理第i行第m列时state的低位可能对应第m列但处理第i1行第1列时低位应该对应第1列。如果你不重排状态换行后状态位和实际格子位置就对不上了结果全错。一个常见的处理办法是换行时把state整体右移一位或左移一位把最高位或最低位的“伸下来的竖骨牌”信息挪到正确的位置。具体方向取决于你实现时状态位的排布顺序。我习惯用“低位对应当前正在处理的列”这种方式这样每次处理完一列下一位自然就是下一个格子换行时只需要把state左移一位即可。如果你用固定的全局列编号那状态位和列号始终对应根本不需要换行重排——我就是这么实现的。4.2 奇偶性剪枝一个廉价但有奇效的预判断所有骨牌问题都有一个通用的必要条件棋盘格子总数必须是偶数否则不可能铺满。这个条件在代码里一句话就能判断if (n * m % 2 ! 0) return 0;但还有一个更强但我见过很多人忽略的判断棋盘黑白染色后黑白格子数必须相等。对于任意形状的棋盘来说这个条件并不总是等价于总数是偶数。举个例子一个2×3的棋盘缺了一个角的形状总数是5显然不行但总数是偶数的异形棋盘也可能黑白不等。好在我们处理的是标准矩形所以黑白染色条件和总数偶数条件是等价的做奇数判断就够了。真正有意义的奇偶性优化藏在3×n的“n为奇数时答案为0”里。如果你做3×n的矩阵快速幂n为奇数时可以直接返回0省掉一整套矩阵乘法。这个结论用黑白染色加个简单推导就能得到考试时如果能快速反应过来能省不少时间。4.3 高精度与取模的时机骨牌数的增长速度非常快。以2×n为例它就是斐波那契数列n50时已经超过10^10n100时超过10^20n×m的增长更夸张。实际题目里一般会给出模数要求比如对1e97取模但如果没有模数要求就得自己实现高精度。我的习惯是设计算法阶段完全不考虑取模先用64位整数在小数据范围内验证正确性确认转移方程没有遗漏后再在累加的地方加上取模。不要把取模运算塞进初始推导里否则最后查错时需要同时排查“逻辑bug”和“取模bug”两类问题非常头疼。如果题目真的要求输出完整的大整数Java的BigInteger或Python的原生大整数会非常省心。C就得自己写高精度加法不过骨牌问题只需要加法所以实现起来并不是很复杂只是编码量会膨胀。5. 实战中怎么用这些递推与状态转移你可能会问这类问题在实际竞赛和面试里到底怎么考最常见的变化是把棋盘改成缺了一些格子或者将骨牌换成L形、T形等多格骨牌。这些变化看起来五花八门但核心解法从未变过找出最小的状态维度构造合法的转移。5.1 残缺棋盘的改造示例假设2×n的棋盘里有一个格子被删掉了问铺法总数。这种题看着吓人其实只要把被删掉的格子位置考虑进去状态重新定义就可以了。因为2×n本身状态只有一维加了残缺后一个直观做法是按照“残缺格是否在上一列/下一列”增加额外状态但更通用的做法是直接退回到轮廓线dp——2×n本来就是轮廓线dp的一个特例把列数m固定为2轮廓线上的状态就是2位二进制。残缺的格子可以视为一个“不能被覆盖”的障碍物处理时直接跳过即可。从这个角度看你会明白为什么竞赛选手遇到骨牌变形题都会先想轮廓线dp——因为它不仅能处理完整矩形还能顺带处理障碍物、边界缺口等不规则情况。唯一要注意的是有了障碍物之后原先“n为奇数时答案为0”这类对称性结论就不一定成立了不能盲目套用。5.2 转移矩阵的重复利用3×n的矩阵快速幂看起来炫技但本质上是把“递推”升级成了“幂运算”。如果题目给你多组询问每组询问有不同的n但棋盘宽度固定为3那么你可以预先把转移矩阵算好然后用倍增法预处理矩阵的2^k次幂每个询问O(8^3 log n)快速回答。这种方法在“同一棋盘宽度、多个n”的场景下特别实用。如果棋盘宽度也是变化的那就没有这么好的预计算机会了老老实实对每个询问跑一次轮廓线dp并且根据n和m的大小关系把较小的那个当作宽度因为轮廓线dp的复杂度是O(n×m×2^min(n,m))量级宽度选小的能显著降复杂度。我做过一个n×m的题n1e9、m4当时直接对n用矩阵快速幂m4意味着状态数是16转移矩阵是16×16log(1e9)次矩阵乘法完全能扛住。如果反过来n4、m1e9那就把棋盘旋转90度让宽度变成4再用同样的方法。旋转棋盘是一个常被忽略但极其有效的优化手段。5.3 状态转移表在预处理阶段把转移对全部算出来无论是3×n还是n×m我强烈建议在预处理阶段就把每一个状态的所有合法转移对列出来而不是在主循环里临时判断。理由有两个第一主循环里每次都判断边界条件会拖慢速度第二把转移逻辑集中在预处理里代码可读性更高查错也更容易。对于3×n状态只有8个枚举所有state和next_state组合再dfs判断能否从当前state通过放置骨牌到达next_state即可。对于n×m状态数是2^m预处理转移对的数量可能很大但m通常不超过10所以完全存得下。边长更长的棋盘预处理表的意义就更明显了。写转移表的时候我习惯把每个状态的合法转移存成vector例如vectorint trans[1 MAXM]; for (int state 0; state (1 m); state) { for (int next_state 0; next_state (1 m); next_state) { if (can_trans(state, next_state, m)) { trans[state].push_back(next_state); } } }can_trans函数的实现就是你dfs铺设的过程返回能否合法转换。然后主循环就变成了for (int state 0; state (1 m); state) { long long val dp[cur][state]; if (!val) continue; for (int ns : trans[state]) { dp[cur ^ 1][ns] (dp[cur ^ 1][ns] val) % MOD; } }清爽很多而且不容易漏转移。这种“预处理转移表主循环极简”的模式几乎可以套用到所有状态压缩dp里不仅限于骨牌问题。5.4 一个值得手推的边界例子初学者最容易卡住的地方是n3、m4和n4、m3的结果为什么都是11。有人会觉得棋盘只是旋转了答案当然一样但如果你手动模拟一遍轮廓线dp的过程会发现扫描顺序完全变了但状态转移最终给出了相同的数值。这是因为旋转不改变棋盘的对称性铺法数量自然不变。这个问题里dp对旋转的对称性是一个很好的自检手段。另外n3、m5的答案是0这个结论用奇偶性判断最快3×515是奇数。但如果不做这个预判断直接跑轮廓线dp代码一样会输出0只是多算了15个格子的无用功。这也侧面说明奇偶性剪枝的意义更多是性能而非正确性。6. 骨牌问题背后更广的dp思维方式骨牌问题之所以能在经典dp题单里活这么多年不止因为它能变出无数个版本更因为它几乎包含了状态压缩dp的所有核心要素状态定义、转移枚举、边界处理、位运算优化。掌握了这道题很多其他二维铺砖、路径计数、覆盖类问题都会变得熟悉。我个人的体会是骨牌问题教会我的最重要的一件事是永远不要试图用大脑维护整个棋盘的状态而是要找到那个“唯一需要被记住的局部信息”。2×n只需要记住当前列是否完整3×n需要记住一列里每个格子的占用情况n×m需要记住一条轮廓线上的占用情况。每升一个维度需要记住的信息变多一点但背后“只留最小必要信息”的原则始终没变。这个原则在真实工程项目里也很有用。比如你在做一个类似俄罗斯方块的游戏要判断某个形状能否放入当前局面本质上就是在一个二维棋盘上做覆盖判断状态压缩的思路完全可以直接迁移。再比如一些资源分配、排班、任务调度问题当你发现暴力做法是枚举所有组合时想一想能不能用“当前已分配哪些资源”作为状态位很多看似困难的问题就能转化成熟面孔的dp。如果你现在正在刷题准备面试我建议把2×n、3×n、n×m三道题放在一个晚上连续刷完每一道都手写状态转移公式不留死角。刷完之后你对“状态设计”这四个字的理解会上一个台阶。最后再分享一个我自己踩过的坑写矩阵快速幂的时候记得把矩阵乘法里的取模放到累加之后否则频繁取模会拖慢速度还有可能因为中间结果溢出导致WA。这个坑在3×n这种小矩阵上不明显但一旦状态数扩大到16或32溢出就很容易出现了。