企业官网建设流程全解析

最近整理动态规划专题的时候，又把 Tri Tiling 这道经典题拿出来刷了一遍。同一道题在几个老牌 OJ 上都有收录，编号分别是 1143 和 2663，题面非常简短：用 1×2 的骨牌铺满 3×n 的棋盘，问有多少种不同的铺法。乍一看和经典的 2×n 铺砖差不多，但真到自己动手推导的时候才会发现，3 行这个高度让状态一下子复杂了不少。这道题不仅是递推入门的绝佳素材，也是理解“为什么要引入额外状态”的好例子，适合刚学完基础 DP、想加深对递推理解的同学，也适合准备机试刷题的人。

1. 题目到底是什么：Tri Tiling 的问题定义与输入输出

1.1 原题在说什么

题目给一个整数 n，要求计算用若干个 1×2 的矩形骨牌完整覆盖一个 3×n 矩形棋盘的方法总数。骨牌只有两种摆放方式：横放占 1 行 2 列，或者竖放占 2 行 1 列。棋盘本身大小固定为 3 行，n 列，n 的范围一般给到 30 左右。

这里最容易劝退新手的点在于，2×n 的铺砖问题里，最右边一列要么竖放一块骨牌，要么横放两块骨牌，状态非常清晰。但是 3×n 里，如果最右边一列直接竖放一块骨牌，它会同时占掉两行，剩下的一行格子就成了一个“孤立点”，必须和左边某一列的格子拼成横放骨牌，这就会把左边已经覆盖好的部分重新“扯开”。换句话说，3 行的高度使得很多铺法不再能简单地切成若干个独立的 3×2 小块，而是会出现跨越多列的连锁结构。这个特性，是整道题推导的核心难点。

1.2 输入输出格式与边界条件

题目采用多组测试数据，每组一行一个整数 n，读到 -1 时结束。n 的范围在 0 到 30 之间，n=0 也是一种合法输入，答案是 1，表示“空棋盘什么都不用铺”这一种方案。这个边界很多人不理解，后面我会专门解释。

几个关键样例值可以提前列出来，方便后面推导验证：

可以看出来，n 为奇数时答案全是 0。原因很简单：3×n 的棋盘一共有 3n 个格子，1×2 骨牌每块覆盖 2 个格子，所以 3n 必须是偶数，n 必须为偶数。这个特判虽然简单，但经常有人忘记，导致后面递推数组访问了一堆奇怪的项。

1.3 为什么 3×n 比 2×n 麻烦

2×n 的递推是 f[n] = f[n-1] + f[n-2]，斐波那契式地往右扫描，每一列都可以独立决定。而 3×n 的问题里，单列竖放会带来“伸出”到旁边的缺口。你可以把这种缺口理解为一种“未完成状态”，它不能只用“已经完整铺好前若干列”来描述，还必须额外记录当前列的缺口长什么样。这就引出了两条路：一条是聪明的递推公式，一条是更通用的状态压缩 DP。

先说结论：这道题最后可以整理成一个非常简洁的递推式，f[n] = 4*f[n-2] - f[n-4]。但如果你只背这个公式，等于完全没理解 Tri Tiling。因为真正值钱的是推导过程，尤其是那个“2”和那个“减号”是怎么冒出来的。

2. 递推关系的建立：从手工画图到完整公式

2.1 从 n=2 和 n=4 开始找感觉

先看最小的偶数 n=2。3×2 的棋盘一共 6 个格子，需要 3 块骨牌。手工画一下，一共只有 3 种铺法：第一种是 3 块骨牌全部横放，铺满两列；第二种是左边一列竖放一块，右边剩余区域再用两块骨牌补成 L 形；第三种是第二种的左右镜像。很多人把这 3 种记成“基本块”，也就是一个宽度为 2 的独立单元。

再看 n=4。如果我们简单粗暴地认为 3×4 可以由两个 3×2 基本块拼接而成，那方法数就是 3×3=9。但真实答案是 11，说明还有 2 种铺法没法切成两个宽度为 2 的小块。这两种铺法就是所谓的“连锁咬合”结构，它们横跨了第一列到第四列，中间那条分界线根本切不开。

这 2 种结构大概长这样：左上角先横放一块骨牌占住第一行前两格，然后剩下的空间用竖放和横放交错填满，最终整体像一个向左突起的 L 形和一个向右收口的 L 形互相卡住。左右对称，所以是 2 种。这就是 Tri Tiling 最迷人的地方，也是很多人推导时漏项的地方。

2.2 最容易被忽略的“第三种铺法”

如果你只是把 n=4 当成“两个基本块”，你永远不会发现那多出来的 2 种。我当年第一次做这道题时，老老实实画了所有 11 种情况，才发现所谓基本块并不是唯一的组建单元。

一个更好的分类思路是：从左往右看整个棋盘，找到第一个“不能用 3×2 基本块描述”的位置。如果前两列恰好是基本块，那就贡献 3 种，剩下的部分是 3×(n-2) 的完整覆盖；如果前四列不是两个基本块的简单组合，而是那种连锁结构，那就贡献 2 种，剩下的部分是 3×(n-4) 的完整覆盖；如果这种连锁结构一直到前六列才第一次出现，那贡献 2 种，剩下的部分是 3×(n-6) 的完整覆盖，依此类推。

这样就能写出一个带连加的递推式：

f[n] = 3f[n-2] + 2f[n-4] + 2f[n-6] + ... + 2f[0]

这个式子看着复杂，但它解释了那 2 种连锁结构可以出现在任何偶数宽度 k 的位置，而且一旦出现，左边的部分必须是一个完整的 3×(k-2) 覆盖，右边也必须是一个完整的 3×(n-k) 覆盖。中间的连锁结构本身只有左右对称的 2 种。

2.3 完整递推式推导：从连加到二阶递推

上面的连加式虽然正确，但写代码时每次都要累加，不够优雅。更漂亮的形式可以通过相邻项相减得到。

先写出 f[n] 和 f[n-2] 的表达式：

f[n] = 3f[n-2] + 2f[n-4] + 2f[n-6] + ... + 2f[0]

f[n-2] = 3f[n-4] + 2f[n-6] + ... + 2*f[0]

用第一个式子减去第二个式子，右边大部分项会消掉：

f[n] - f[n-2] = 3f[n-2] + 2f[n-4] - 3f[n-4] f[n] - f[n-2] = 3f[n-2] - f[n-4]

移项整理，就得到：

f[n] = 4*f[n-2] - f[n-4]

这个公式简洁得不像话，但它的前提是 n 为偶数，且初值 f[0]=1，f[2]=3。用 n=4 验证：f[4] = 43 - 1 = 11，正确。用 n=6 验证：f[6] = 411 - 3 = 41，正确。

这个二阶递推的漂亮之处在于，它把之前那个“特殊连锁结构可能出现在任意位置”的复杂情况，浓缩成了一个负号。负号本质上是在做“去重”：3*f[n-2] 里多算了那些连锁结构从 n-4 位置开始的重复情况，所以要减掉 f[n-4]。

2.4 验证 n=6 的答案

为了确保推导没出错，我们可以用组合的方式再算一遍 n=6。

3×6 可以由三种东西组成：宽度为 2 的基本块（3 种）、宽度为 4 的连锁结构（2 种）、宽度为 6 的连锁结构（2 种）。枚举组合：

• 三个基本块，每块 3 种：3^3 = 27 种。
• 一个基本块加一个宽度为 4 的连锁结构，位置有 2 种选法，基本块 3 种，连锁结构 2 种：2×3×2 = 12 种。
• 一个宽度为 6 的连锁结构：2 种。

总数就是 27 + 12 + 2 = 41 种，和递推公式算出来的一致。到这一步，递推式才算是真正站稳了。

3. 代码实现与常见套路

3.1 基于递推式的 C++ 实现

有了递推式，代码非常短。我习惯先把 0 到 30 的答案全部离线算好，然后根据输入直接查表输出。n 的范围很小，这样做最省事，也能避免多组测试数据时反复计算。

#include <iostream> #include <vector> using namespace std; int main() { vector<long long> f(31, 0); f[0] = 1; f[2] = 3; for (int i = 4; i <= 30; i += 2) { f[i] = 4 * f[i - 2] - f[i - 4]; } int n; while (cin >> n && n != -1) { if (n & 1) { cout << 0 << endl; } else { cout << f[n] << endl; } } return 0; }

这里用 long long 而不是 int，主要是不想纠结边界问题。n=30 时答案大概是 2.99 亿，int 理论上也能存住，但中间计算 4*f[i-2] 时会超过 10 亿，虽然还没溢出，可一旦题目以后把范围调大，int 就容易翻车。用 long long 一劳永逸。

3.2 用状态压缩 DP 一劳永逸地解决

如果你不想背递推式，或者担心自己推导时漏掉连锁结构，可以直接换一种思路：按列做状态压缩 DP。对于 3 行的棋盘，每一列用 3 位二进制表示这一列哪些格子已经被覆盖，状态范围只有 0 到 7。

核心思想是：从左往右扫描列，dp[i][mask] 表示前 i 列已经全部铺满，并且有 mask 中对应位置是从第 i 列“伸到”第 i+1 列的水平骨牌时，当前有多少种方案。初始状态 dp[0][0] = 1，表示第 0 列前面没有任何伸出来的骨牌。每次枚举当前列的 mask，尝试用横放、竖放把所有空格填满，生成下一列的 nextMask。

用 DFS 枚举当前列内部的填法：

void dfs(int row, int mask, int nextMask, long long ways) { if (row == 3) { dp[col + 1][nextMask] += ways; return; } if (mask & (1 << row)) { dfs(row + 1, mask, nextMask, ways); } else { // 竖放，占用当前行和下一行 if (row + 1 < 3 && !(mask & (1 << (row + 1)))) { dfs(row + 1, mask | (1 << (row + 1)), nextMask, ways); } // 横放，向右伸到下一列 dfs(row + 1, mask, nextMask | (1 << row), ways); } }

然后在主循环里对每一列、每一个 mask 调用这个 DFS。最终答案是 dp[n][0]，表示铺完 n 列后没有任何骨牌伸到 n+1 列。这个方法对 3×n、4×n 甚至 m×n 都通用，只是状态数随行数指数增长。平时做题时，我会先用这种状态压缩 DP 对拍小数据，再去验证手推的递推式是否正确。

3.3 复杂度与打表技巧

递推实现的复杂度是 O(n)，空间可以压到 O(1)，只要记住最近两个偶数项即可。状态压缩 DP 的复杂度约 O(n × 状态数 × 转移数)，对于 3 行棋盘状态数只有 8，转移也很有限，跑 n=30 绰绰有余。

由于这道题是多组输入，最好的做法就是在 main 函数开头先把表打好，之后每个测试用例直接 O(1) 输出。打表还有一个好处：可以肉眼检查几个关键值。我每次写完都会先看 n=4 是不是 11、n=6 是不是 41，如果这两个值不对，那递推式一定有问题。

4. 踩坑记录与调试心得

4.1 奇数 n 直接输出 0，别忘特判

虽然 n=1 和 n=3 在打表数组里天然是 0，但你不一定保证每次查询前数组都初始化过。更严谨的做法是在拿到 n 之后先判断奇偶。我见过有人把递推公式写成 f[i] = 4*f[i-2] - f[i-4]，然后在循环里只处理偶数 i，结果忘了 f[1]、f[3] 没有赋值，数组默认值又不是 0，导致输出一堆随机数。所以要么全局变量自动清零，要么在输出前显式判奇偶。

另外，n=0 是合法输入，答案 1，不要因为“没有棋盘”就输出 0。我在初学时就栽过这个跟头，后来把 0 到 6 的预期结果贴在注释里，才彻底杜绝这种低级错误。

4.2 多组测试数据的读取

题目要求读到 -1 结束。推荐写法是while (cin >> n && n != -1)。不要写成while (cin >> n, n != -1)，逗号表达式的语义很容易出问题。如果你用 C 的 scanf，可以写成：

while (scanf("%d", &n) == 1 && n != -1)

这样能保证输入读取成功才进入循环。多次提交时，最常见的错误就是循环条件写错，导致第一组数据输出完直接跳出，或者把 -1 也当成合法数据参与计算。

4.3 f[0]=1 到底怎么理解

这是新手问得最多的地方。f[0]=1 不是说“空棋盘有 1 种奇怪摆法”，而是把它当成递推的乘法单位元。就像组合数学里 C(n,0)=1 必须为 1 一样，当我们把问题拆成“铺完左边的基本块，右边剩一个 3×0 的空区域”时，右边什么都不做就是一种方案。如果 f[0]=0，那么 f[2]=3*f[0] 就会变成 0，整个递推链直接断掉。所以边界值不是算出来的，是为了让公式闭合而定义出来的。

4.4 数组越界与溢出隐患

用f[i] = 4*f[i-2] - f[i-4]时，循环从 i=4 开始，i-4 最小是 0，没有越界问题。但如果你写成f[i+2] = 4*f[i] - f[i-2]，就一定要保证 i 从 2 开始，否则会访问 f[-2]。这类偏移错误特别隐蔽，尤其在循环变量边界差 1 的时候。建议多打印几个中间值，或者直接用前面说的离线打表法，把循环次数写死，避免边界算错。

4.5 调试方法：对拍和手工枚举

如果你还是不确定递推式对不对，可以写一个暴力搜索来对拍。因为 n 很小，DFS 枚举所有放法也不会超时。把暴力结果和递推结果放在一起比较 n=2、4、6、8，只要这几个值全对，后面基本不会错。我通常会在代码里临时加一个断言：

assert(f[4] == 11); assert(f[6] == 41); assert(f[8] == 153);

这样每次运行都会自动检查关键点，省心很多。

5. 从这道题看递推与状态设计

5.1 三个典型递推模型对比

Tri Tiling 很适合放在递推专题里做横向对比。2×n 的铺砖是一阶线性递推，f[n] = f[n-1] + f[n-2]；3×n 是偶数项上的二阶递推，f[n] = 4*f[n-2] - f[n-4]；4×n 就更复杂了，不仅递推阶数更高，还可能出现更多“咬合”结构。如果只死记公式，很容易混淆。建议把每个模型对应的棋盘结构画一遍，尤其是 3×n 里的连锁结构，画过一次就不会再忘。

5.2 如何快速判断是否能用递推

判断一个铺砖问题能否用一维递推解决，关键看两点：第一，行数是否固定且很小；第二，是否存在“无法切成独立小块”的连锁结构。如果连锁结构只有有限种形态，通常可以通过增加辅助状态或构造高阶递推来搞定。但如果形态很多，更高阶的递推公式会非常丑陋，这时候老老实实上状态压缩 DP 反而更不容易出错。

一个实用的经验是：先尝试把问题拆成“基本块 + 特殊块”，如果特殊块种类很少，就手动推导递推式；如果特殊块越来越多，马上转头用状态压缩 DP，不要在一个公式上死磕。

5.3 扩展思考：4×n 和更复杂的轮廓线 DP

Tri Tiling 的进阶方向是 4×n 甚至 m×n 的骨牌覆盖。4×n 同样可以用状态压缩 DP 解决，状态数是 2^4=16，转移可以在预处理时枚举出来。如果行数增加到 10 以上，状态数会变成 1024，仍然可以跑；但如果你遇到的是 n、m 都特别大的情况，就需要把状态转移写成矩阵，然后用矩阵快速幂加速。这也是 Tri Tiling 这类入门题真正的价值：它让你意识到，一个看似简单的递推背后，其实藏着一整套“按列扫描 + 状态压缩 + 矩阵加速”的方法论。

我个人在实际做题中的体会是，递推式 f[n] = 4*f[n-2] - f[n-4] 可以帮你快速 AC，但真正让你能力提升的是那个“从连加到相减”的推导过程。每次重做这道题，我都会把 n=4 的 11 种铺法重新画一遍，提醒自己不要只满足于 AC 的快乐。最后再分享一个小技巧：遇到这种范围小、多组输入的题，永远先把答案表打了，一遍过，别在循环里反复算。