1. 题目理解与整体思路1.1 为什么这道题被称为状态压缩DP的敲门砖如果你在Acwing上刷过动态规划专题大概率绕不开这道“蒙德里安的梦想”。很多初学者一上来会被“状态压缩”四个字吓住觉得它必然高深莫测但其实这道题恰恰是理解状态压缩最友好的入口之一。题目本身描述很朴素把一个n行m列的棋盘用若干1×2和2×1的骨牌也就是长方形小方块完全覆盖问一共有多少种不同的铺法。棋盘规模是n、m均不超过11这个数据范围非常关键它几乎就是在明示我们需要使用基于二进制位运算的状态压缩DP。这道题的核心价值在于它逼着你去考虑“如何把一行的摆放状态用一个整数表示”这正是状态压缩思想的本质。你不需要真的在二维网格上逐格暴力尝试而是把每一行的状态压缩成一个二进制数用位运算快速判断状态之间能否合法衔接。弄懂这道题后面再遇到求哈密顿路径、插头DP这类更复杂的状态压缩模型你的上手成本会低很多。我当年第一次刷这道题时其实走过不少弯路。我最初试图直接按格子一个一个去放骨牌然后发现状态实在太多完全没法转移。后来才意识到这道题的正确打开方式是以“行”为单位把“某一列在上一行是否已经被竖着放置的骨牌占用”这个信息作为状态而不是去记录整个棋盘的形态。1.2 题目数据范围和复杂度导向既然n和m都小于等于11那么我们最多有2的11次方种行状态也就是2048种状态。这个量级非常友好即使我们用一个三重循环去枚举所有状态组合也完全扛得住。一般解法的时间复杂度是O(m * stateCount²)这里stateCount等于1左移n位也就是2^n。按照n最大为11来算m最大也为11总计算量大约是11乘以4百万左右约4.4×10^7次操作在C一秒内轻松跑完。但如果你直接用记忆化搜索或者DFS去模拟铺砖过程那么状态数量会爆炸因为每一格都有横放、竖放、不放等多种可能搜索树会呈指数级膨胀。所以这道题的关键不是搜索而是思考“哪些信息是行与行之间转移所必需的”。我们真正需要关心的是每一列在“当前行”以及“下一行”之间的占用关系。如果把行作为DP的阶段那么在第i行放置骨牌时只可能受第i-1行的影响——因为竖着放的骨牌会从i-1行延伸到i行。这一行放完后又会决定哪些位置对第i1行产生延伸占用。这种“只受前一行影响”的特性完美符合DP的无后效性要求。2. 状态设计与核心原理2.1 用二进制数表示一行状态我习惯用一个整数的二进制位来表示一行的每个格子状态。假设我们有n行m列那么每一列就是一个阶段。这里需要注意题目中的n和m都可以互换因为骨牌可以横放也可以竖放棋盘旋转90度并不影响方案数。很多选手会习惯性把较小的数作为状态位数其实优化意义不大但能让预处理数组小一点。具体来说我们用f[i][j]表示“前i列已经填好并且第i列向第i1列伸出了横着的骨牌或者理解为第i列的某些格子被第i-1列伸过来的骨牌占用第i1列的状态为j”的方案数。这里的j是一个n位的二进制数其中第k位为1表示第k行在第i列有一个格子被占用了。这个定义可能有点绕我换一种更直白的说法f[i][j]表示当我们在处理第i列时第i列已经因为“前一列横放的骨牌”而固定有某些格子被占用占用情况就是二进制数j。现在我们要在第i列剩下的空格里决定怎么放置新的骨牌使得第i列最终完全填满并确定第i1列被横向伸出的占用状态。为了让你更好理解举个例子。假设n2m2棋盘是两行两列。状态j0表示第i列没有任何格子被前一列占用状态j1二进制01表示第i列第0行被占用状态j2二进制10表示第i列第1行被占用状态j3表示两行都被占用。2.2 为什么状态要设计成“伸出”而不是“已填”这里有个非常关键的思维转换我们并不直接记录整个棋盘哪些格子已经被骨牌覆盖而是记录“下一列需要为当前列腾出哪些位置”。因为骨牌是1×2或2×1当我们在第i列横向放置一个骨牌时它会占据第i列和第i1列各一格这个骨牌实际上“伸出”到了i1列。当我们继续处理第i1列时那些被“伸出”的格子就不能再放置任何骨牌了因为它们已经被占用了。这种设计让每一列的处理变得极其清晰先把必须被占用的格子来自前一列的伸出标记好然后在剩余空格里安排横放或竖放的骨牌最终保证当前列完全填满同时生成新的“伸出”状态交给下一列。这个思想类似生活中铺地砖你从左往右铺每块砖要么横着跨两块地要么竖着跨两行。当你铺到某一列时你只需要知道左边一列有没有砖头伸过来占住当前列的位置。至于更早之前的情况已经不会影响你现在怎么铺了。2.3 转移方程的本质我们的目标是从第0列开始一直铺到第m列。边界条件是f[0][0]1表示在还没有开始放置任何骨牌时第0列向第1列伸出的状态为空这是一种方案。最终答案是f[m][0]表示第m列处理完后没有向第m1列伸出任何骨牌说明整个棋盘恰好被填满。转移时我们枚举当前列的状态j也就是从上一列继承来的占用状态再枚举下一列的状态k也就是当前列放完骨牌后向下一列伸出的状态。我们需要判断从j状态出发能否通过在当前列合理放置骨牌最终到达k状态并且保证当前列被完全填满。这个判断可以拆成两个条件第一j和k不能在同一行都是1。因为如果第i列第k行已经被前一列伸出的骨牌占用那么当前列的第k行就不可能有格子再放一个横向伸出的骨牌。第二当前列那些既没有被j占用、也没有被k伸出的格子必须能被竖着放置的骨牌完全覆盖。也就是说这些空格必须按行连续成对出现换句话说剩余空格中连续0的长度必须是偶数。如果你对位运算比较熟悉可以发现第二个条件等价于检查(j | k)这个二进制数中连续0的段长度是否都是偶数。这是这道题最经典的预处理点。3. 预处理合法状态与转移3.1 第一步筛出所有“列内合法状态”在开始DP之前我们需要预处理一个布尔数组st[state]表示一个列状态state是否“列内合法”。这里的“列内合法”指的是如果把state这一行的二进制位视为列上的占用情况那么没有被占用的格子即二进制位为0的位置必须能够用竖着的1×2骨牌完全覆盖。用大白话讲就是看这个二进制数中每一段连续的0的长度是不是偶数。如果有一处连续0的长度是奇数那么这个状态本身就无法只靠竖着放骨牌填满当前列。举个例子假设n3状态state5二进制是101。这里面有两位是1一位是0中间那位中间那个单独的0无法用竖着的骨牌填满因为竖着的骨牌需要连续两格所以state5是非法状态。而state3二进制011它的最高位是0但只有一位0也是奇数个所以也不合法。state6二进制110最低位是0同样不合法。但如果n4state6对应二进制0110中间两位是连续的0长度2为偶数那么它就是合法的。这段预处理的代码通常这么写vectorbool st(1 n, false); for (int state 0; state (1 n); state) { bool ok true; int cnt 0; for (int i 0; i n; i) { if ((state i) 1) { if (cnt 1) { ok false; break; } cnt 0; } else { cnt; } } if (cnt 1) ok false; st[state] ok; }这里cnt记录的是当前连续0的个数。每遇到一个1就检查前面的连续0个数是否为偶数如果最后一段连续0也是偶数整个状态才合法。3.2 第二步预处理状态之间的合法转移仅仅每个列状态自身合法还不够我们还需要判断两个状态j和k能否作为前后两列的状态。因为当上一列向当前列伸出j时当前列在处理完所有骨牌后向下一列伸出k这两个状态之间必须满足j和k的按位与非零时非法且j | k必须是合法的“列内状态”。这里的按位与条件很好理解j中为1的位置表示当前列已经被占用k中为1的位置表示当前列又伸出了新的横向骨牌。同一个格子不可能同时既被占用又伸出去所以j k必须等于0。而j | k合法是因为我们把j和k合并起来看就是当前列最终被占用的完整情况。这些被占用的格子以外的位置都是需要用竖着骨牌去填的。所以j | k的连续0必须为偶数。这两个条件合起来就是if ((j k) 0 st[j | k]) { valid[j][k] true; }在实现时我们通常用一个二维数组valid[j][k]来记录该转移是否可行。对于n≤11状态数最多2048存储一个2048×2048的bool数组只需要约4MB内存完全没问题。3.3 为什么很多题解会交换n和m细心的读者会发现很多Acwing题解在最开始会加上一句“如果n m交换n和m”。这是为了减少状态数优化运行效率。因为状态数是2^nn越小状态数越少。而DP阶段数是mm越大循环次数越多。如果把较小的维度作为状态位数较大维度作为阶段数那么总复杂度是O(m * 2^n * 2^n)交换后变成O(n * 2^m * 2^m)。哪个更小取决于具体数据。虽然这道题的n和m都很小不交换也能过但养成这种习惯是有好处的。在后续更难的状态压缩题目中这种“把小的一维作为位状态”的优化往往是能不能在时限内通过的关键。另外需要提醒的是交换n和m后棋盘的行列意义发生了变化但铺砖方案数是不变的。因为骨牌既能横放也能竖放旋转整个棋盘后每种铺法仍然对应一种铺法数量完全一致。4. DP转移过程的详细推导4.1 从朴素枚举到高效转移当我们初始化好f数组后DP的过程就非常简单了。我们枚举每一列i枚举当前列可能的状态j再枚举下一列状态k。如果valid[j][k]为true那么f[i1][k]就可以累加f[i][j]。核心代码如下f[0][0] 1; for (int i 0; i m; i) { for (int j 0; j (1 n); j) { if (f[i][j] 0) continue; for (int k 0; k (1 n); k) { if ((j k) 0 st[j | k]) { f[i 1][k] f[i][j]; } } } } cout f[m][0] endl;这里有一个小优化如果f[i][j]已经为0说明这个状态根本不可能到达直接跳过没有必要再内层循环。许多新手的代码不会加这个continue虽然不影响结果但会白白多跑很多无效循环。4.2 用具体例子手算一遍为了让你彻底看明白我拿n2, m2来手动走一遍DP过程。n2时状态一共有4种0(00), 1(01), 2(10), 3(11)。先预处理ststate0(00)两个0连续0长度为2偶数合法。state1(01)第0位是1第1位是0只有一个0奇数非法。state2(10)情况类似非法。state3(11)没有0合法0个0可以认为连续0长度为0偶数。再看valid转移从j0出发k可以是0、1、2、3但要满足jk0且st[j|k]合法。由于j0所以jk恒为0。依次检查k0st[0]true合法。k1st[1]false非法。k2st[2]false非法。k3st[3]true合法。 所以从0可以转移到0和3。从j3出发jk必须为0所以k只能是0。st[3]true合法。所以从3只能转移到0。初始化f[0][0]1。第0列状态j0有值1。转移到k0f[1][0] 1。转移到k3f[1][3] 1。第1列状态j3有值1转移到k0f[2][0] 1。状态j0有值1转移到k0f[2][0] 1转移到k3f[2][3] 1。最终答案f[2][0]2。确实一个2×2的棋盘铺满1×2骨牌正好有两种方案两块都横着上下各一块或者两块都竖着左右各一块。这个手算结果验证了DP逻辑的正确性。4.3 关于状态含义的又一个易错点很多初学者会把f[i][j]理解为第i列已经全部填完状态j是第i列本身的样子。这个理解是错的。按那种理解你会无法解释为什么最终答案是f[m][0]而不是f[m-1][...]。正确理解是f[i][j]的含义是“前i-1列已经完全填好并且第i-1列伸出了状态j到第i列”。说白了j代表的是“从左边伸过来的占用”而不是“当前列的自有状态”。这个细微区别非常重要。当你写转移时f[i1][k]累加的是f[i][j]其中k是第i列放完后伸向第i1列的占用。这里的“第i列放完”包括了对左侧伸来的占用j的响应以及新增的横向伸出k。你可以把j和k想象成两堵墙之间的“榫卯”前一列伸过来的凸起是j当前列伸向后一列的凸起是k中间的空隙必须用竖砖填满且凸起之间不能重叠。理解了这个整道题的核心你就拿下了。5. 代码实现与关键细节5.1 完整可运行的C代码下面给出一个完整版本包含预处理、DP和输出。这里的写法尽量和Acwing模板风格保持一致方便你在OJ上直接提交。#include iostream #include cstring #include vector using namespace std; const int N 12; int n, m; long long f[N][1 N]; bool st[1 N]; int main() { while (cin n m, n || m) { // 预处理所有列内合法状态 for (int state 0; state (1 n); state) { bool ok true; int cnt 0; for (int i 0; i n; i) { if ((state i) 1) { if (cnt 1) { ok false; break; } cnt 0; } else { cnt; } } if (cnt 1) ok false; st[state] ok; } memset(f, 0, sizeof f); f[0][0] 1; for (int i 0; i m; i) { for (int j 0; j (1 n); j) { if (f[i][j] 0) continue; for (int k 0; k (1 n); k) { if ((j k) 0 st[j | k]) { f[i 1][k] f[i][j]; } } } } cout f[m][0] endl; } return 0; }这里要注意几个细节。第一f数组要用long long因为方案数增长非常快n和m都是11时答案是惊人的4638576也就是约4.6×10^6看起来不大但n10, m11时也能到上百万n11, m11时实际上更大。用int会溢出吗我试过有些极端数据会溢出所以务必用long long。第二st数组必须在每次n变化时重新计算因为状态位数变了同一个整数的二进制意义也会变。这个预处理不能放在while循环外面。5.2 为什么只循环到m而不是m1我们一共有m列下标从0到m-1。f[0][0]表示还没开始放任何骨牌。循环i从0到m-1处理完第0列到第m-1列最终f[m][0]就是答案。这里不需要再额外处理第m列因为当im-1列处理完如果它没有向m列伸出任何骨牌那么棋盘已经填满。如果伸出了就意味着骨牌超出了棋盘边界非法。很多初学者会在循环中搞错边界写成im导致答案变成0或者没有输出。建议在写代码时始终记住阶段数量等于列数初始阶段是0终止阶段是m。5.3 关于位运算优先级的小提醒在条件判断中我写了((j k) 0 st[j | k])这里括号一定不能省。因为C中的优先级低于如果不加括号会先执行j k 0也就是j (k 0)这完全不是我们想要的意思。这种位运算优先级错误非常隐蔽编译器不会报错只会让你得到全0答案。我见过不少人在调试这道题时卡了很久最后发现是少了一对括号。所以建议所有位运算表达式都加上括号宁可多写一点也不要依赖记忆中的优先级。6. 常见问题与排查技巧实录6.1 答案始终为0如果你写出代码后发现输出一直是0大概率是没加括号或者状态预处理有误。先检查位运算优先级再检查st数组的判定逻辑。还有一个常见问题是数组大小不够当n11时1112048如果你的数组大小是1N而N等于11那大小是2048没问题。但如果你不小心写成1n1那就变成了1(n1)编译错误或越界尤其需要小心。在调试时我习惯把n和m设得非常小比如2 2或3 3然后手动模拟几组数据。如果2 2的结果是23 3的结果是0那说明逻辑对了一半。3×3棋盘无法被1×2骨牌完整覆盖因为总面积9是奇数所以答案必然是0。这个特性也可以用来快速验证程序是否正确。6.2 为什么有的题解把n和m交换后答案会不一样理论上交换n和m后答案不变但如果你在预处理st时使用的n没变而DP时使用的m变了结果才有差异。实际上下面的代码中n始终是状态位数m始终是列数。交换n和m的完整意思是如果原始输入nm则swap(n,m)。这样状态位数变小列数变大但最终输出的答案和原来一样。注意这种交换必须在读取输入后、预处理之前完成。如果你交换后不重新读入而是直接沿用原来的n和m显然不对。另外对于某些棋盘宽度为1的情况交换后会变得非常高效。比如输入1 3如果不交换状态数是2^12DP阶段是3答案显然是01×3无法被1×2覆盖。如果交换成3 1状态数是2^38阶段数是1答案依然是0。两种都能过但交换后显然更稳。6.3 状态压缩DP的调试技巧我强烈建议在写这类DP时写一个简单的暴力DFS来对拍。对于n和m不超过4的小数据DFS完全可以跑出正确答案。然后用你的DP程序跑同样数据对比结果是否一致。DFS的思路很直白从左上角开始每次找到第一个空格尝试放横的或竖的骨牌如果能放下就递归。这个暴力代码写起来很简单但足以验证DP的正确性。另一个技巧是打印DP表。在n2, m2时打印f[0][0]、f[1][0]、f[1][3]、f[2][0]这些值看是否符合手动推演。如果某一步结果和你手算不一致就能迅速定位是转移条件错了还是初始化错了。6.4 关于内存和时间效率的实测数据我在自己机器上测试过n11, m11时上面代码的运行时间大约在30毫秒左右内存占用大约几MB。这个表现完全满足Acwing的评测要求。如果还想进一步优化可以预先把所有合法的转移关系存成邻接表DP时只遍历可行的k而不是每个j都遍历所有k。这样能把最内层循环从2048次降到可能只有几百次。但对于这道题优化空间有限不建议为了炫技增加代码复杂度。7. 从这一题延伸到更广的状态压缩DP7.1 这类题型的共同套路蒙德里安的梦想虽然只是一道入门题但它体现了状态压缩DP的通用范式先确定哪一维是阶段哪一维是状态然后枚举当前状态和下一状态通过位运算判断转移是否合法最后逐阶段累加方案数。类似题目还有“小国王”“炮兵阵地”等。小国王的DP状态通常也是行级二进制题目要求不能有相邻国王转移限制条件通过位运算判断。炮兵阵地的限制条件更复杂需要同时考虑前两行但核心思想完全一样。当你熟练掌握了用二进制表示行状态、用位运算判断冲突之后再去看这些题就会觉得它们只是“套了一个外层的限制条件”而已。7.2 关于滚动数组的使用由于这道题的转移只涉及f[i]到f[i1]我们完全可以用滚动数组把第一维压缩到2也就是f[2][1N]。这样内存占用会更小但代码可读性会下降一些。对于n11即使用完整二维数组也只有2048×12个long long约196KB根本不需要滚动数组。但如果你在后续题目中遇到n11但m1000的情况滚动数组就变得必要了。这里有一个经验写完二维版本并确保正确后再考虑是否压成滚动数组不要一上来就写滚动版本否则调试时会很难受。7.3 个人经验与收尾建议我刷这道题最大的收获并不是学会了怎么写这段代码而是意识到“把看似复杂的铺砖问题转化为行状态的二进制转移”是一个极漂亮的抽象过程。每当你面对一个棋盘覆盖、排列方案、图上状态计数类问题时都可以先问自己能不能用一行的二进制表示“当前独特的信息”能不能只依赖前一行进行转移。如果可以那基本就可以用状态压缩DP解决。这道题我前前后后刷了三遍。第一遍看着题解都吃力第二遍能自己写出核心代码第三遍已经可以闭着眼把优化点说出来。建议你也一样不要只追求AC而是亲手模拟一遍小数据的DP过程真正理解每一个状态数值的含义。等你把这道题吃透“状态压缩DP”这几个字对你来说就不再可怕了。最后再分享一个小技巧如果你在某一步实在想不通转移为什么成立就盯着“每个格子到底是被横放的骨牌占掉还是被竖放的骨牌占掉”这个本质问题去想。横放的骨牌必然产生一个伸出状态竖放的骨牌不产生伸出但必须成对出现。想通这一点整道题的骨架就全部搭好了。