Tri Tiling骨牌覆盖：从状态压缩DP到递推式的完整推导

如果给你一个宽度为 (n)、高度为 3 的矩形棋盘要求用若干个 (1 \times 2) 的骨牌把它完全铺满问一共有多少种不同的铺法这个问法正是 HDU-1143 / POJ-2663 这道名为 Tri Tiling 的经典题目。它看着像个小学奥数题实际却是不少算法竞赛选手第一次接触“逐列状态压缩 DP”和“线性递推”的启蒙题。n 通常只到 30 左右数据范围不大但它背后的状态机建模思路以及如何从 8 个状态硬生生压出一条干净的递推式 (f(n)4f(n-2)-f(n-4))非常值得掰开揉碎讲一遍。这篇文章不只给出能 AC 的代码更想带着你把“为什么要这样递推”“递推式到底从哪来”彻底讲明白让这道题真正变成你自己的工具。1. 题目到底在问什么3×n 棋盘的骨牌覆盖先对齐一下题意。输入会给出很多行每行一个整数 (n)表示棋盘的宽度也就是棋盘尺寸为 (3 \times n)。你要用若干个 (1 \times 2) 的骨牌去覆盖这个棋盘骨牌可以横着放也可以竖着放要求不重叠、不遗漏地把所有格子铺满。对于每个 (n)输出不同覆盖方案的数量。这里有两个容易忽略的细节。第一题目是多组数据读到 (-1) 才结束而不是读到 0 结束。第二(n0) 时按 1 种方案处理也就是“空棋盘”本身算一种覆盖方式。很多新手第一次写这题卡在输入上或者卡在 (n0) 的特判上都是很常见的事。题目给的范围一般很小常见是 (0 \le n \le 30) 左右所以它不算一道“难在数据规模”的题真正难的是建模思维。如果你只会跟着别人的题解背递推式那下次换成 (4 \times n)、(5 \times n) 或者任意宽度 (M \times N) 的棋盘覆盖你还是不会。所以我会从最朴素的枚举思路开始一步步引出状态机再引出递推式。1.1 一个最小的例子3×2 的三种铺法先看最简单的非平凡情况(3 \times 2) 的棋盘也就是高 3 格、宽 2 格。这个棋盘一共有 6 个格子需要 3 块骨牌。可以画出三种铺法三块骨牌全部横着放上下三行各放一块。上、中两格被一块竖骨牌占掉下格横着放一块第二列的下格再横着放一块。下、中两格被一块竖骨牌占掉上格横着放一块第二列的上格再横着放一块。换句话说(f(2)3)。这个数字很关键它是递推式的初值之一。你可能会想(3 \times 2) 只有 3 种那 (3 \times 4) 是不是直接 (3 \times 3 9) 种答案是 11 种多出来的 2 种来自跨越中间两列的交错结构这就是这题有意思的地方。1.2 空棋盘算一种n0 的约定很多 DP 题的边界都是“空状态的方案数为 1”这题也一样。(f(0)1) 表示宽度为 0、也就是没有任何格子的棋盘你什么都不做也算一种合法的“覆盖方式”。这个约定不是拍脑袋定的它在递推里非常自然当某一侧已经完全铺满时剩下的空棋盘必须被计为 1否则递归就会断掉。所以前几项应该是n0123456f(n)103011041奇数位置全是 0这不是巧合下面马上解释。2. 两个快速判定为什么奇数 n 直接输出 0先处理最简单的情况如果 (n) 是奇数不用跑任何 DP直接输出 0 就行。这背后有两个层次的论证一个比一个深刻。2.1 面积论证格子总数必须是偶数每块 (1 \times 2) 骨牌覆盖 2 个格子所以棋盘的总格子数必须是偶数。(3 \times n) 的总格子数是 (3n)要让 (3n) 是偶数只能让 (n) 是偶数。这个论证很直观小学生都能理解但它只说明“必要”不说明“充分”。也就是说 (n) 是偶数时可能有解也可能没解还需要进一步判断。2.2 染色论证黑白格数量必须相等把棋盘按黑白相间的方式染色。每个 (1 \times 2) 骨牌无论横着放还是竖着放永远恰好覆盖一个黑格和一个白格。因此如果棋盘能被完全覆盖那棋盘上的黑格数和白格数必须完全相等。现在算一下 (3 \times n) 棋盘的黑白差。以左上角为黑格开始染色一行一行的黑白分布会交替变化。仔细数一下会发现当 (n) 是奇数时黑格数比白格数多 3 或者少 3反正不可能相等。这就从更深的组合性质上说明了奇数无解。这个“染色法”值得记住。以后遇到任何覆盖类问题第一反应就应该是先看看两种颜色的格子数量平不平衡很多时候能直接秒杀一大半情况。3. 从“手数方案”到“逐列状态机”偶数 (n) 有了解但怎么计数最朴素的想法是枚举第一列的覆盖情况然后递归处理剩余部分。但 Tri Tiling 的坑在于覆盖方案里存在“跨越多列的交错结构”你没办法简单地按两列一组拆开。看 (3 \times 4) 的 11 种方案如果前两列总是一个完整的 (3 \times 2) 块那方案数就应该是 (3 \times 3 9)。但实际有 11 种说明存在 2 种方案它们的骨牌从前两列“伸”到了后两列里形成了一种类似互锁的结构。这种结构用简单的分块讨论很难讲清楚容易漏数。那就换个思路不要从左往右一块一块地分块而是从第一列开始一列一列地扫描用状态记录“当前这一列被上一列伸过来的骨牌占了多少”。3.1 状态编码mask 表示“被左边伸进来的骨牌盖住的格子”从左往右扫的时候真正需要关心的不是整个棋盘而是“当前正在处理的这一列里的格子哪些已经被左边的骨牌覆盖了”。每一列恰好有 3 个格子从上到下编号。我用一个 3 位二进制掩码 mask 来表示这一列的预覆盖状态从右边数第 1 位十进制 1表示最上面的格子已被覆盖第 2 位十进制 2表示中间格子已被覆盖第 3 位十进制 4表示最下面格子已被覆盖。比如 mask1表示当前列只有最上面的格子已经被左边伸进来的横骨牌盖住剩下中间的格子和最下面的格子需要在本列处理中覆盖。如果 mask0表示当前列没有任何格子被预覆盖整列 3 个格子都是空的。这样处理的好处是处理当前列时我们只需要考虑 mask 里那些为 0 的格子如何覆盖。覆盖方式只有两种竖着放一块骨牌占据同一列相邻的两个空格横着放一块骨牌占据当前格子同时向右边伸一格这样就会在下一列对应位置留下一个预覆盖位。当前列处理完以后所有为 0 的格子必须变成已覆盖而那些横着伸出去的骨牌会组合成新的 mask作为下一列的预覆盖状态。3.2 八个状态的全部转移因为一列只有 3 个格子mask 总共只有 8 种可能从 0 到 7。这 8 个状态之间能走通的边非常少我直接把完整转移表列出来这是整道题的核心当前 mask可以得到的下一列 mask说明01中、下两格竖放上格横伸04上、中两格竖放下格横伸07三格全部横伸10中、下两格竖放16中、下两格分别横伸40上、中两格竖放43上、中两格分别横伸70当前列已满无需操作34下格横伸61上格横伸25上、下两格分别横伸52中格横伸这里有几个值得注意的“陷阱转移”从 mask2也就是中间格子已经被覆盖那么剩下的上格和下格不相邻它们两个都不能竖放只能各自横着伸到下一列所以只能转移到 mask5。从 mask5也就是上格和下格已经被覆盖中间格子只能横着伸到下一列所以只能转移到 mask2。这两个转移比较隐晦很多初写状态机的人都容易漏。3.3 逐列扫描的 DP 过程有了转移表DP 就顺理成章了。定义 (dp[i][mask]) 表示处理完前 (i) 列之后第 (i1) 列的状态为 mask 的方案数。初始时 (dp[0][0]1)也就是第 1 列左边没有骨牌伸进来。然后对每一列拿当前所有状态去尝试转移累加到 (dp[i1][\text{mask}])。最终处理完 (n) 列之后要求第 (n1) 列的状态必须是 0也就是没有任何骨牌超出棋盘右边界答案就是 (dp[n][0])。我用 (n2) 演示一遍(dp[0][0]1)。处理第 1 列从状态 0 分别转移到 1、4、7所以 (dp[1][1]dp[1][4]dp[1][7]1)。处理第 2 列状态 1 转移到 0 和 6状态 4 转移到 0 和 3状态 7 转移到 0。最终 (dp[2][0]3)正好是 (3 \times 2) 的答案。这个 DP 的复杂度是 (O(n \times 8 \times 8))常数小到可以忽略。4. 把 8 个状态压成一条递推式f(n)4f(n-2)-f(n-4)有了状态机其实你已经能 AC 了。但很多题解到这里直接丢出一个递推式[ f(n)4f(n-2)-f(n-4), \quad n \ge 4 ]这个式子怎么来的为什么系数是 4为什么还要减一项如果只是背下来下次遇到 (4 \times n) 还是不会。我们花点时间把它完全推导出来。4.1 符号约定与关系式为了推导方便给状态机里的每个状态计数一个符号(A_ndp[n][0])(B_ndp[n][1])(C_ndp[n][4])(D_ndp[n][7])(E_ndp[n][3])(F_ndp[n][6])(G_ndp[n][2])(H_ndp[n][5])根据棋盘上下对称(B_nC_n)(E_nF_n)。这个对称能省不少事。现在把转移表翻译成等式。目标状态 0 可以从 1、4、7 这三个状态转移过来所以[ A_{n1}B_nC_nD_n2B_nD_n ]目标状态 1 可以从 0 和 6 转移过来所以[ B_{n1}A_nF_nA_nE_n ]目标状态 7 只从 0 转移过来[ D_{n1}A_n ]目标状态 3 只从 4 转移过来[ E_{n1}C_nB_n ]注意最后一个式子里因为 (E_nF_n)所以 (F_{n1}B_n) 也一样成立。这几个关系式已经足够推出最终递推了。4.2 消元得到线性递推把 (E_n) 换掉。由 (E_{n1}B_n) 可知 (E_nB_{n-1})所以[ B_{n1}A_nB_{n-1} ]等价地把下标整体平移一下[ B_nA_{n-1}B_{n-2} ]再由 (D_nA_{n-1})代入 (A_{n1}2B_nD_n)[ A_{n1}2B_nA_{n-1} ]这个式子下标整体减 2就得到另一个关系[ A_{n-1}2B_{n-2}A_{n-3} ]也就是[ 2B_{n-2}A_{n-1}-A_{n-3} ]现在回到 (B_nA_{n-1}B_{n-2})两边同时乘 2[ 2B_n2A_{n-1}2B_{n-2} 2A_{n-1}A_{n-1}-A_{n-3} 3A_{n-1}-A_{n-3} ]最后把 (2B_n) 代回 (A_{n1}2B_nA_{n-1})[ A_{n1}3A_{n-1}-A_{n-3}A_{n-1} 4A_{n-1}-A_{n-3} ]假设 (kn1)那么[ A_k4A_{k-2}-A_{k-4} ]这里的 (A_k) 就是 (f(k))所以[ f(n)4f(n-2)-f(n-4) ]递推式就这么出来了。整个过程没有任何玄学就是老老实实消元。4.3 验证前几项用递推式验证前面手算的几项(f(0)1)(f(2)3)(f(4)4f(2)-f(0)4 \times 3 - 1 11)(f(6)4f(4)-f(2)4 \times 11 - 3 41)(f(8)4f(6)-f(4)4 \times 41 - 11 153)结果完全吻合。这下可以放心用了。5. 参考实现递推版和状态机版5.1 递推版代码这道题因为 (n) 很小最简单的做法是把所有答案预计算出来#include cstdio long long f[64]; int main() { f[0] 1; f[2] 3; for (int n 4; n 64; n 2) { f[n] 4 * f[n - 2] - f[n - 4]; } int n; while (scanf(%d, n) 1 n ! -1) { if (n 1) { printf(0\n); } else { printf(%lld\n, f[n]); } } return 0; }这里的数组多留了一点余量就算题面范围比 30 稍大一些也够用。注意循环步长是 2只填偶数下标奇数下标保持 0。5.2 状态机版代码如果你想真正体验“状态压缩”的思路或者以后要改造成任意宽度的骨牌覆盖题那我推荐你写这个版本#include cstdio #include cstring long long dp[64][8]; int to[8][8]; void init_trans() { to[0][1] to[0][4] to[0][7] 1; to[1][0] to[1][6] 1; to[4][0] to[4][3] 1; to[7][0] 1; to[3][4] 1; to[6][1] 1; to[2][5] 1; to[5][2] 1; } int main() { init_trans(); int n; while (scanf(%d, n) 1 n ! -1) { if (n 1) { printf(0\n); continue; } memset(dp, 0, sizeof(dp)); dp[0][0] 1; for (int i 0; i n; i) { for (int s 0; s 8; s) { for (int t 0; t 8; t) { dp[i 1][t] dp[i][s] * to[s][t]; } } } printf(%lld\n, dp[n][0]); } return 0; }这个代码看起来比递推版啰嗦但它的通用性更强。你把高度从 3 改成 4状态从 8 变成 16转移表重新推一遍就能解决 (4 \times n) 的同类问题。5.3 复杂度分析递推版预处理是 (O(\text{MAXN}))每次查询是 (O(1))。状态机版每次计算 (O(n \times 8 \times 8))应付 (n \le 30) 完全没问题。理论上如果 (n) 大到 (10^9)就需要用矩阵快速幂了这部分我在第 7 节补充。6. 实测中容易踩的坑这类老 OJ 题虽然简单但有几个细节特别容易让人当场卡住。6.1 输入是以 -1 结束的多组数据这是最经典的坑。很多新手看到题目说“输入 0 结束”结果用while (scanf(%d, n) ! EOF n ! 0)然后 n0 出去答案就全错了。Tri Tiling 的终止条件是 -1不是 0n0 是一个正常询问需要输出 1。读取时一定要写成n ! -1。6.2 n0 别慌输出 1如果你把 (n0) 当作边界判成 0或者程序里没有初始化 (f[0]1)那 (f[2]) 也会算错。递推式的正确性建立在 (f[0]1) 上这一步错了后面全错。6.3 奇数下标不要硬塞递推递推式只在偶数下标上成立。有人写循环时写成for (int i 2; i n; i) f[i] 4 * f[i-2] - f[i-4];然后下标从 1 开始全乱套。建议直接if (n 1)输出 0再用步长为 2 的循环处理偶数。6.4 不要迷信 intlong long 更稳虽然原题范围下 int 也勉强够但 (f(34)) 已经接近 41 亿超过 32 位有符号整数的上限。谁也不能保证你遇到的是哪一年的数据、范围改没改过直接用 long long 就没有这个烦恼。6.5 预计算尽量提前做多组数据题目不要每组都重新 DP 一遍尤其不要每组都做一遍状态机的三重循环。一次性把f[0..MAXN]算好之后每组输入都是直接查表又快又保险。这个习惯在比赛里能省下不少时间。7. 从 Tri Tiling 到更大的一盘棋骨牌覆盖问题家族Tri Tiling 只是骨牌覆盖问题大家族里的一个小成员把它吃透之后你会发现很多题都是同一套思路。7.1 2×n 的斐波那契高度为 2 时(2 \times n) 用 (1 \times 2) 骨牌覆盖答案就是斐波那契数列(f(n)f(n-1)f(n-2))。这个大家都很熟。高度为 2 时状态机的状态更少只有 4 个最后能压出的递推也更简单。高度为 3 时递推从一阶变成二阶本质上是同一个故事。7.2 4×n 以及任意宽度的轮廓线 DP当高度变成 4(4 \times n) 的覆盖序列是 1, 1, 5, 11, 36, 95, ... 这里面的递推式要复杂得多而且很难用人肉推导得到。这时候逐列状态机就成了标准解法。高度固定为 (M) 时状态数量是 (2^M)转移矩阵是 (2^M \times 2^M)用矩阵快速幂就能处理很大的 (n)。Tri Tiling 里面 8 个状态、12 条转移是你理解这套通法最好的起跳板。7.3 如果 n 很大矩阵快速幂如果 (n) 变成 (10^9) 甚至 (10^{18})直接递推和直接逐列 DP 都不可行。好在递推式已经拿到设 (g(m)f(2m))那么[ g(m)4g(m-1)-g(m-2) ]写成矩阵形式[ \begin{bmatrix} g(m) \ g(m-1) \end{bmatrix}\begin{bmatrix} 4 -1 \ 1 0 \end{bmatrix} \cdot \begin{bmatrix} g(m-1) \ g(m-2) \end{bmatrix} ]初始值是 (g(0)1)(g(1)3)。用快速幂 (O(\log n)) 就能算出任意大的偶数 (n)。如果题目要求取模直接在矩阵乘法里取模即可这也是“计算理论与算法分析设计”里经常要展示的从 DP 到递推再到矩阵加速的完整链路。我自己做这道题的时候最大的体会是递推式不要死记状态机也不要觉得麻烦。你花十分钟把那张转移表画出来之后不管是写暴力 DP、推线性递推还是改造其他棋盘覆盖题都会顺很多。遇到同类问题时先快速判断奇偶能剪掉一半数据再看宽度和高度范围决定是直接 DP 还是上矩阵快速幂。这种“先定性、再建模、再优化”的思路比背任何题解都有用。