企业官网建设流程全解析

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]就是答案。计算一下：n=1是1种，n=2是2种，n=3是3种，n=4是5种，n=5是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列全部铺满，且第i+1列受到“从左往右伸出来的横骨牌”影响后的状态为state时的方案数。这里的state是一个3位二进制数，bit为1表示对应的行被来自左边的一个横骨牌占据了。换句话说，处理完前i列之后，第i+1列上已经有某些格子被占掉了，这些格子不能再放新骨牌。

初始时dp[0][0] = 1，也就是还没开始铺，第1列没有被任何伸出的骨牌占据。目标是dp[n][0]，即铺完前n列且没有骨牌伸到n+1列去。

2.2 转移规则：四种放置动作

从dp[i][state]转移到dp[i+1][next_state]，我们要在第i+1列上填补那些state中为0的位置，并决定是否往第i+2列伸出新的横骨牌。具体有4种动作：

1. 竖放：在第i+1列中，某个高度为2的连续空格区域放一块2×1骨牌。这个动作只影响当前列的两个位置，把它们从0变成1，不会影响第i+2列。
2. 横放（右伸）：在第i+1列中，某个空格位置放一块1×2骨牌，骨牌横跨第i+1列和第i+2列的同一行。这个动作把当前列的该位置从0变成1，同时把第i+2列同一行的位置置为1。
3. 跳过填空：如果state中第k位已经是1，说明该位置被来自左边的横骨牌覆盖了，无需处理。
4. 当前列填满后，剩余state中为0的位置若无法通过上述动作覆盖，则此转移非法。

用一个具体例子来感受。假设当前state = 001，表示第i+1列最下面一行已经被左边的横骨牌占了。那么第i+1列还剩下上面两行是空的：

• 上面两行是连续的2格，可以竖着放一块2×1，把这两个格子填掉。此时第i+1列全部为1，且没有往第i+2列伸出的部分，所以next_state = 000。
• 也可以在上面两行分别横放骨牌，往第i+2列伸出两块横骨牌，此时next_state = 011（第i+2列的第1、2行被占）。
• 注意这里两块横骨牌必须同时出现，因为上面两行的空格是两个相邻但各自独立的行位，如果只放一块横骨牌，另一行就没法覆盖了。

再比如state = 010，表示中间行被占，剩下第1行和第3行两个空格。这两个空格是不连续的，无法竖放一块2×1。唯一的办法是第1行和第3行分别横放，向右伸到第i+2列，所以next_state = 101。如果state = 011，只剩第1行空格，只能横放一块，next_state = 100。

这个逻辑写成代码，可以直接用DFS对每一列做填充枚举，也可以在预处理阶段枚举所有state和next_state的合法转移对。后者更快，因为3位的二进制数一共只有8个状态，转移对最多也就8×8=64个，直接打表。

2.3 从状态转移到矩阵快速幂

当n比较小的时候，直接for i从1到n，做dp[i+1][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[i+1] = M × dp[i]

于是dp[n] = M^n × dp[0]。矩阵快速幂的复杂度是O(8^3 log n)，非常快。

我实际测试的时候，构建转移矩阵有个小陷阱：state和next_state谁是行谁是列容易搞反。这里建议统一成矩阵M[state][next_state]，乘的时候是dp[i+1][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的铺法中，最后一列的覆盖方式需要更仔细地分类，这个递推式的推导过程比较容易写错，所以我更推荐直接用状态压缩+矩阵快速幂的通用解法，它天然不会漏情况。

n=2时答案是3，n=3时答案是0，n=4时答案是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)，它只有四种可能被覆盖的方式：

1. 已经被来自上方的骨牌覆盖，也就是说state中对应j这一位是1，此时不能放新骨牌，直接跳到下一个格子，同时把当前行的这一位变成0（表示这个格子已经处理完，不再对后续有影响）。
2. 被来自左侧的骨牌覆盖，这个信息体现在上一格处理完后的state更新中。实现时通常在转移时判断左格是否被横骨牌覆盖。
3. 放一块竖着的2×1骨牌：要求当前格子为空、下一行的同一列也是空的（在n×m的边界内）。放完后，轮廓线上这一位变成1，表示下方格子被覆盖了。
4. 放一块横着的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位（竖放）或第j+1位（横放）置1。因为当前格一旦扫过，它就不再属于轮廓线，只有它伸出去影响后面的部分才需要保留。

如果直接按上面的实现跑，你会发现n=2、m=3的输出是3，n=3、m=3的输出是0，和理论值是一致的。这里强调一下，轮廓线dp的状态数是指数级的2^m，所以m一般不能超过10到12，否则需要改成插头dp或使用更高阶的优化，不过那就是另一个话题了。

3.4 如何验证自己的dp没写错

写这类dp最怕不是不会转移，而是转移里有一两个case漏了，答案差一点你自己还发现不了。我的建议是：先用暴力搜索（DFS回溯）算小棋盘的结果，和dp结果对拍。棋盘大小从1×1开始，逐行逐列扩大，对到3×4以上基本就可以确信dp写对了。

暴力方法也很直接：找棋盘上第一个没被覆盖的格子，尝试放横骨牌或竖骨牌，递归继续，最后统计完整铺满的路径数。这个暴力的复杂度极高，但用来验证dp绰绰有余。

我放一个参考数值表，方便你自检：

4×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行的最后一列跳到第i+1行的第一列时，state的每一位含义整体右移/左移了一格（取决于你的状态压缩顺序）。比如你在处理第i行第m列时，state的低位可能对应第m列，但处理第i+1行第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为例，它就是斐波那契数列，n=50时已经超过10^10，n=100时超过10^20；n×m的增长更夸张。实际题目里一般会给出模数要求（比如对1e9+7取模），但如果没有模数要求，就得自己实现高精度。

我的习惯是：设计算法阶段完全不考虑取模，先用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的题，n=1e9、m=4，当时直接对n用矩阵快速幂，m=4意味着状态数是16，转移矩阵是16×16，log(1e9)次矩阵乘法完全能扛住。如果反过来n=4、m=1e9，那就把棋盘旋转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，例如：

vector<int> 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 一个值得手推的边界例子

初学者最容易卡住的地方，是n=3、m=4和n=4、m=3的结果为什么都是11。有人会觉得棋盘只是旋转了，答案当然一样，但如果你手动模拟一遍轮廓线dp的过程，会发现扫描顺序完全变了，但状态转移最终给出了相同的数值。这是因为旋转不改变棋盘的对称性，铺法数量自然不变。这个问题里，dp对旋转的对称性是一个很好的自检手段。

另外，n=3、m=5的答案是0，这个结论用奇偶性判断最快：3×5=15是奇数。但如果不做这个预判断，直接跑轮廓线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，溢出就很容易出现了。