如果你在 AcWing 上刷到 291 题《蒙德里安的梦想》大概率已经对状态压缩 DP 有所耳闻。这道题被很多人称为“状压 DP 的敲门砖”因为它把状态设计、位运算、预处理、DP 递推这些核心能力全揉在了一张棋盘上。题目本身不复杂——用 1×2 的长方形骨牌铺满 N×M 的棋盘问有多少种铺法。但就是这道看似普通的铺瓷砖题能让不少人卡上好几天。今天我把这道题的完整思路、实现细节和踩坑经验从头到尾捋一遍希望能帮你少走点弯路。适合刚学会背包、线性 DP 想进阶状压的读者也适合已经会做但没梳理清楚“为什么这么设计状态”的同学。1. 题目到底在问什么先吃透“铺瓷砖”的数学模型1.1 题目长啥样一个“铺瓷砖”的数学模型题目名称里的“蒙德里安”指的是荷兰画家皮特·蒙德里安他的画风大家应该都见过——红黄蓝的色块黑色线条把画面分割成大小不一的矩形格子。用 1×2 的骨牌去铺满一个棋盘铺完之后的棋盘横竖分明的样子确实有点蒙德里安作品的意思。具体题目描述很简单给定一个 N 行 M 列的棋盘用若干个 1×2 和 2×1 的长方形骨牌铺满整个棋盘问一共有多少种不同的铺法。注意骨牌可以旋转1×2 横着放就是覆盖同一行的相邻两列2×1 竖着放就是覆盖同一列的相邻两行。棋盘上每个格子必须且只能被覆盖一次也就是“刚好铺满”。这道题在 AcWing 上的编号是 291属于算法提高课“状态压缩 DP”章节的经典题目。我第一次做的时候第一反应是这不就是 DFS 搜索吗从左上角开始一块一块摆摆不下去就回溯。但题目数据范围是 N 和 M 最大等于 11棋盘格子最多 121 个直接搜肯定会炸。那怎么优化答案是把“这一列怎么放”看成一个整体用二进制数表示它。1.2 为什么不能暴力搜索从复杂度聊起很多人一看到“铺瓷砖”就想着 DFS我先把这个想法掐灭。假设棋盘是 10×10总共 100 个格子需要 50 块骨牌。每个骨牌都可以横放或竖放搜索树的分支因子至少是 2那最坏情况下要枚举 2^50 种方案大约是 10 的 15 次方量级。就算剪枝剪掉大半这个规模也完全跑不动。更关键的是DFS 回溯的过程中同一个铺法会被重复计算很多次比如棋盘左上角的一块区域无论后面怎么铺只要前面铺法相同后面就会重复探索。这种“重叠子问题”的特征天然就是 DP 的猎场。但 DP 也有一个问题状态怎么表示如果按普通二维网格做线性 DP一个格子放横骨牌会影响右边一格放竖骨牌会影响下边一行信息跨行跨列很难用简单的 dp[i][j] 表示。这时候就需要状态压缩——把某一行或某一列的选择情况压缩成一个整数的二进制位。这种“用整数的 bit 表示一个集合”的技巧就是状态压缩 DP 的核心。2. 状态压缩 DP 的切入方式状态怎么定才不重不漏2.1 让“横着放”拿主意状态设计的核心思路状态压缩 DP 的设计难点不在于位运算本身而在于“阶段选什么、状态记录什么”。这道题有一个非常漂亮的切入角度只决定横向骨牌的位置竖向骨牌自动填补剩余空位。为什么可以这样因为横骨牌是“跨列”的它从第 i 列伸到第 i1 列会同时占用两列的格子而竖骨牌是“同列内”的它在某一列内占住连续两行。一旦我们把所有横向骨牌的位置定下来棋盘剩下的所有空格子就只有一种填法——用竖骨牌去填。如果能填满这个方案就合法如果哪一列剩下奇数个连续空格或者空格不连续那就说明这种横骨牌布局不合法。你可以这样理解横骨牌是“决策”竖骨牌是“检查”。横骨牌怎么放才能不重叠竖骨牌怎么放才能铺满这两个问题被拆开了。而“横向骨牌的位置”恰恰可以用一个二进制数精准表达——某一行有横骨牌伸到下一列该位就记为 1否则记为 0。2.2 状态定义与转移方程把“铺”变成递推公式这道题最经典的状态定义是f[i][j] 表示前 i-1 列已经全部摆好并且第 i-1 列有横向骨牌伸到第 i 列这些伸出的骨牌所在的行构成的状态为 j 的方案数。这里 j 是一个 n 位二进制数n 是棋盘行数。如果 j 的第 k 位是 1说明第 k 行有一个横向骨牌从第 i-1 列伸到了第 i 列。为什么要这么定义因为 DP 按列递推我处理到第 i 列时最关心的就是“上一列有哪些横向骨牌伸过来了”。这些伸过来的骨牌会占用第 i 列的某些格子所以第 i 列的所有格子并不都是空白的我需要知道它们位置。一张二进制表就够了。转移方程写出来非常简洁f[i][j] Σ f[i-1][k]其中 k 是第 i-2 列伸到第 i-1 列的状态j 是第 i-1 列伸到第 i 列的状态。k 和 j 之间要满足两个条件(j k) 0同一行不能同时有伸进来的骨牌和伸出去的骨牌否则两个横骨牌会在同一个格子里重叠。st[j | k] truej | k 代表了第 i-1 列中所有被横骨牌占据的格子剩下的空格子必须能被竖骨牌完整填满。初始化是 f[0][0] 1表示第 0 列之前没有棋盘也不会有骨牌伸到第 0 列。最终答案是 f[m][0]表示处理完第 m-1 列后没有任何骨牌伸到第 m 列棋盘正好全部铺满。2.3 两条合法性规则一次想清楚后面少返工很多初学者写这道题卡就卡在 st 数组的判断上。st[j] 的含义是这一列的状态为 j 时列内空格是否合法。具体来说如果这一列某些行被横骨牌占据不管是伸进来的还是伸出去的剩下的空格子如果要被竖骨牌填满就必须满足每一段连续空格的个数都是偶数。竖骨牌是 1×2 竖直放置的骨牌它在同一列内占连续两行。所以一个空格段如果有 3 个连续空格其中必然有一个格子没法被竖骨牌覆盖如果一个空格段中间被横骨牌隔断那就得分别判断各段。代码里用一个 cnt 变量统计连续空格的个数遇到横骨牌时检查 cnt 是否为偶数然后清零重新计数最后还要检查末尾一段。这个逻辑听上去简单但很多人第一次写会漏掉末尾检查导致状态 100二进制 100只有中间一行有横骨牌上下各一个空格被误判为合法。第二个条件是 (j k) 0这个很容易理解。j 表示第 i-1 列伸到第 i 列的横骨牌k 表示第 i-2 列伸到第 i-1 列的横骨牌它们可能在同一个格子重叠。比如某一行 k 的当前列位置有骨牌伸进来占了一格而 j 又在这一行放了一个横向骨牌从当前列伸出去那这两个骨牌就在同一个格子里“撞车”了必须禁止。理解了这两个条件整个题目的核心就已经拿下了一半。3. 完整实现预处理 DP 循环一步步搭出来3.1 第一步只找“状态友好”的列状态写代码之前我建议先把 st 数组预处理出来。这个数组记录的是对任意一个 n 位二进制状态 i它对应的列内空格是否合法。处理方式就是逐位扫描遇到 1 就检查之前连续 0 的个数是不是偶数然后清零遇到 0 就计数加一。扫描结束后再检查末尾的连续 0 段。这一步的代码很经典for (int i 0; i 1 n; i) { int cnt 0; bool ok true; for (int j 0; j n; j) { if (i j 1) { if (cnt 1) { ok false; break; } cnt 0; } else { cnt; } } if (cnt 1) ok false; st[i] ok; }有一点需要注意这里 n 是棋盘的行数也就是二进制状态的长度。如果预处理时把 n 和 m 搞混代码会在运行时报数组越界或者结果完全不对。我在初学阶段就因为这个浪费过很长时间。预处理做完之后可以把所有合法状态打印出来验证一下。n3 时合法状态应该有 0000、3011、6110等而 1001、2010、4100、5101都不合法因为列内会留出奇数个连续空格。3.2 第二步DP 主循环与答案提取代码这样写最清晰预处理完 st 数组之后DP 主体就非常机械了。我习惯用三重循环直接写代码结构清晰也容易调试#include bits/stdc.h using namespace std; typedef long long ll; const int N 12, M 1 N; int n, m; ll f[N][M]; bool st[M]; int main() { while (cin n m, n || m) { // 预处理 st for (int i 0; i 1 n; i) { int cnt 0; bool ok true; for (int j 0; j n; j) { if (i j 1) { if (cnt 1) ok false; cnt 0; } else { cnt; } } if (cnt 1) ok false; st[i] ok; } memset(f, 0, sizeof f); f[0][0] 1; for (int i 1; i m; i) { for (int j 0; j 1 n; j) { for (int k 0; k 1 n; k) { if ((j k) 0 st[j | k]) { f[i][j] f[i - 1][k]; } } } } cout f[m][0] \n; } return 0; }这里 f 数组之所以用 long long是因为方案数可能很大。11×11 的棋盘铺法数量非常大int 会溢出即使中间不溢出为了通用性也建议直接用 long long。数组第二维 M 1 NN 取 12这样 112 4096足够容纳 n 最大 11 时的所有状态最多 111 2048。双循环判断时j 是本列伸出的状态k 是上一列伸入的状态。判断条件 (j k) 0 st[j | k] 严格对应前面讲的第二条规则。f[i][j] 从 f[i-1][k] 累加含义是“前 i-1 列都摆好第 i-1 列伸到第 i 列的状态是 j”。答案输出 f[m][0]而不是 f[m][j] 或 f[m-1][0]。为什么f[m][0] 表示第 0 到第 m-1 列都处理完第 m-1 列没有任何骨牌伸到第 m 列说明棋盘右边界外干干净净这就是“全部铺满”的状态。3.3 复杂度能压到多低预处理转移的进阶优化上面这个朴素版本时间复杂度是 O(m × 2^n × 2^n)。n 最大 112^11 20482048×2048 ≈ 419 万再乘 m 的 11约 4600 万次循环。C 跑这个量级完全没问题所以其实直接写也能过。不过如果你想追求更优的常数或者以后在更大的题目里复用这套模板我建议再加一层预处理把每个状态 k 所有可以合法转移到的状态 j 存到 head[k] 数组里。这样 DP 主循环就变成枚举每个 k再遍历它对应的合法 j 列表省去大量无效判断。vectorint head[M]; memset(head, 0, sizeof head); for (int k 0; k 1 n; k) { for (int j 0; j 1 n; j) { if ((j k) 0 st[j | k]) { head[k].push_back(j); } } } memset(f, 0, sizeof f); f[0][0] 1; for (int i 1; i m; i) { for (int k 0; k 1 n; k) { if (f[i - 1][k] 0) continue; for (int j : head[k]) { f[i][j] f[i - 1][k]; } } }注意这里转移方向稍微调整了一下枚举上一列状态 k然后把它贡献给所有合法的当前列状态 j效果和之前一致但省掉了一层无效枚举。head 数组的存法是把 j 存在 head[k] 下面意思是“状态 k 能转移到状态 j”。还有两个常见的输入优化特判。第一个是 if (n * m 1) 直接输出 0因为奇数个格子不可能用偶数的面积和覆盖。第二个是 if (n m) swap(n, m)把较大的数放到 m列数使得状态枚举的位数 n 尽量小。棋盘旋转 90 度后铺法是一一对应的答案不变。这个优化在 n 和 m 差距明显时效果很显著比如 11×9 交换后状态数从 2048 降到 512循环量直接少一大截。4. 实战中一定会踩的坑错误代码与排查经验4.1 高频错误 Top 4我见过最多的报错都在这这道题虽然思路清晰但写起来小坑不少。我整理了一下学员和评论区里出现频率最高的几个错误都列在下面。第一个是数组下标越界或状态位数错误。有人把循环写成 for (int i 0; i 1 m; i)直接把列数 m 当成了二进制位数。如果 n 和 m 恰好差距很大比如 n3, m10那循环会跑到 1024 个状态而 st 只预处理的 8 个状态根本没覆盖结果自然不对。记住状态的每一位对应一行所以状态枚举永远是 1 n。第二个是 st 判断漏掉末尾连续空格。这一点我在前面强调过但还是要再说一遍。比如状态 6二进制 110只有第 0 行是空格长度 1不合法如果你扫描到最后一个 1 后直接结束没检查 cnt状态 6 就会误判成合法导致装填错误。第三个是 f 数组忘记初始化。因为题目是多组数据每组都要重新 memset。只写 f[0][0] 1 而没清空 f[i][j]残留数据会串到下一组结果越跑越离谱。建议每组测试数据进来后先 memset(f, 0, sizeof f)。第四个是 int 溢出。11×11 的合法方案数大约是几百万级别实际上远超 int 范围。我之前用 int 写过一版结果样例能过nm11 时答案变成负数。排查了半天才发现是溢出。记住用 long long别在这上面省。4.2 用最小数据手算验证n2, m3 的例子初学者最怕的就是代码跑出结果但不知道对不对。我强烈建议在写完后先拿小规模数据手算再对照代码输出。拿 n2, m3 举例2 行 3 列的棋盘一共有多少种铺法我们可以直接手数三个竖骨牌竖着放这是一种一个横骨牌加一个竖骨牌横骨牌可以在第一行或第二行也有两种两块横骨牌叠起来再加一个竖骨牌横骨牌放在第一列和第二列或者第二列和第三列又有两种。总数是 3 种。用代码跑出来也应该是 3。如果你跑出来是 1 或者 5那就说明状态定义、转移条件或初始化某一环有问题。再验证 n2, m2答案应该是 2两个竖骨牌或者两个横骨牌。n3, m3 因为格子数是奇数直接输出 0。这些都是很好用的对照测试。4.3 多组输入、奇偶特判等细节问题这道题的输入格式是“多组测试数据每组一行两个整数 n 和 m以 0 0 结束”所以主循环写成 while (cin n m, n || m)。如果你忘了加读入终止条件程序会不停地读下去看起来就像“卡死了”。奇偶特判可以放在读入之后、预处理之前。如果 n*m 是奇数直接 cout 0然后 continue 到下一组数据。这个特判不只是省时间也能避免一些边界情况下的潜在问题。swap 优化要注意必须在读入后立刻执行swap 之后 n 和 m 的含义就变了后续所有循环、状态枚举、答案输出都基于交换后的值。答案不会被影响因为棋盘旋转 90 度后铺法一一对应这一点不用担心。但你心里要清楚调试时看到的“行”和“列”已经交换过了。5. 从这道题还能带走什么状态压缩 DP 的迁移思路5.1 状态压缩 DP 的通用套路从这道题归纳四个步骤刷完蒙德里安的梦想我建议大家顺手做个小复盘把状态压缩 DP 的通用套路总结出来。以后遇到类似题目直接套这个框架。第一步识别问题特征。如果棋盘或集合的规模很小比如 n ≤ 20而且题目需要决策某一行、某一列或某个集合的选中情况那大概率可以用状压。棋盘类题目常按行或列做阶段集合类题目常用“已选集合”做阶段。第二步设计二进制状态。想想当前阶段需要记录什么“残余信息”比如这道题要记录上一列伸过来的横骨牌那些位就是状态。状态设计得越精准转移条件就越简单。第三步预处理合法性。把所有可能的状态枚举出来按题目规则判断是否合法并存到 st 数组或 head 数组里。预处理是状压 DP 的灵魂它会同时影响代码逻辑和运行速度。第四步写递推转移。按阶段从小到达推转移时用位运算快速判断兼容性。初始化一个虚拟的“空状态”最后答案也是某个特定状态通常是 f[m][0] 这种“没有残余影响”的状态。这套四步法可以直接迁移到小国王、玉米田、炮兵阵地这些经典状压题上。尤其是炮兵阵地那道题状态不仅和上一行有关还和上上一行有关但思路还是“先预处理、再按行 DP、用位运算判断冲突”本质上是同一个套路。5.2 我的个人体会与后续练习路线我在带新手刷这道题时最常说的一句话是先别急着写代码把一个状态画在纸上。状态压缩 DP 的难点从来不是代码本身而是你脑子里能不能浮现出棋盘上那个二进制影子。第 i 列哪些格子被横骨牌伸进来占了哪些格子要竖着补哪些格子向右边伸出去——这三类信息全在一个整数里想不清楚就写不出正确的转移。这道题你花半天彻底吃透往后遇到小国王、玉米田、炮兵阵地都会觉得顺理成章。我做这道题时光 2×3、3×3、4×4 的手算答案就验了七八遍不是不自信而是通过小数据验证能帮你确认状态定义和转移是否真的吻合。这种“写代码前先手算写代码后跑小数据对照”的验证能力才是刷算法题最重要的底层技能之一。
