1. 项目概述与问题引入“铺瓷砖”这个题目听起来像是装修工地的活儿但在算法竞赛的语境下尤其是像蓝桥杯国赛这个级别的舞台上它往往是一个披着生活外衣的、对动态规划DP和状态压缩技巧的深度考察。我当年第一次在模拟赛里遇到这类题目时第一反应也是“这不就是排列组合吗”结果一上手就发现状态空间大得惊人暴力搜索根本跑不完。这类问题的核心魅力在于它用一个非常直观的场景——用固定形状的瓷砖铺满一个给定大小的矩形地面——来包装一个复杂的组合数学与状态转移问题。对于Java B组的选手而言这不仅是编程能力的测试更是对思维严谨性、对问题抽象能力以及对经典算法模型灵活运用的一次综合大考。简单来说题目通常会给你一个N x M的网格地面以及一种或几种固定形状的瓷砖比如1x2的长方形砖或者更复杂的L形砖。你需要计算出恰好铺满整个地面不允许重叠不允许超出边界的所有不同铺设方案数。这个“所有不同方案数”就是最终的答案往往是一个巨大的数字需要我们对结果取模。问题的难点从来不在于理解“铺满”这个概念而在于如何高效、无遗漏且不重复地枚举所有可能的铺设状态。当N和M稍微大一点比如达到10这个量级朴素的想法如深度优先搜索DFS会立刻遇到组合爆炸时间复杂度过高。这时状态压缩动态规划状压DP就成了几乎唯一的“标准答案”。在接下来的内容里我不会仅仅给出一个AC的代码模板。那样做意义不大因为下次题目稍微变一下形你可能又不会了。我将带你彻底拆解“铺瓷砖”问题的内核从最基础的思路开始一步步推导为什么需要状压DP如何设计状态如何进行状态转移并针对Java实现中的关键细节和常见“坑点”进行重点剖析。我们会用1x2的砖块即骨牌覆盖N x M棋盘这个最经典的“多米诺骨牌覆盖”问题作为主线因为它涵盖了此类问题的所有核心思想。掌握了它再遇到L形砖、更复杂的棋盘如存在障碍物等变种你都能触类旁通。2. 从暴力搜索到状压DP思路的演进与必然性我们先从一个最直观的解法开始深度优先搜索DFS。想象我们站在棋盘的左上角尝试放置第一块砖。砖可以横着放覆盖两个水平相邻的格子也可以竖着放覆盖两个垂直相邻的格子。我们做一个选择标记这两个格子为已覆盖然后递归地去铺剩下的格子。当所有格子都被覆盖时就找到了一种方案。这个思路完全正确但为什么不行呢核心在于重复计算和状态爆炸。假设棋盘是2 x 3的用1x2的砖去铺。我们手动枚举一下就会发现某些不同的放置顺序最终得到的铺设图案可能是一样的。DFS会把这些顺序都当作不同的搜索路径导致重复计数。更致命的是随着棋盘变大搜索树的分支会呈指数级增长。对于N10, M10的棋盘格子数100即使有各种剪枝搜索空间也依然是天文数字不可能在规定时间内通常1秒完成计算。那么如何避免重复和爆炸我们需要换一个视角。不要从“当前该放哪块砖”的角度思考而是从“当前行的覆盖情况”来思考。这就是按行递推的思想。我们一行一行地铺。当铺到第i行时第i-1行及其以上的所有行必须已经被完全铺满因为砖不会悬空。此时第i行某些格子可能已经被从上一行竖着放下来的砖覆盖了剩下的格子需要我们在本行内通过横放砖块或者和下一行配合竖放砖块来覆盖。如何描述一行的“覆盖情况”我们用状态压缩。用一个M位的二进制数来表示一行中每个格子的状态。通常我们用1表示这个格子已经被覆盖可能是被上一行竖下来的砖盖住了也可能是被本行横放的砖盖住了用0表示这个格子还空着需要被覆盖。注意这个“需要被覆盖”是相对于当前决策阶段而言的。当我们决策第i行时1表示这个位置不能再放砖的起点因为已经被占了0表示这个位置必须被作为某块砖的起点来覆盖要么横放要么和下一行一起竖放。有了这个定义我们就可以设计DP状态了。设dp[i][state]表示铺完前i行并且第i行的覆盖状态为state时所有可能的方案总数。这里state就是那个M位的二进制整数它的二进制表示对应第i行每个格子的“是否已被覆盖”状态。关键转移如何从dp[i-1][prev_state]转移到dp[i][curr_state]这意味着已知第i-1行铺完后的状态是prev_state我们如何摆放砖块使得第i-1行被完全铺满即所有prev_state中的0都必须被填上并且同时决定了第i行的状态curr_state。这个过程可以通过一个DFS函数来枚举。这个DFS不是在全盘搜索而是在两行之间针对特定的prev_state枚举所有可能的砖块摆放方式并计算出每种摆放方式产生的curr_state。具体来说我们从第i-1行的最左边格子开始扫描用列索引j从0到M-1。如果prev_state在第j位是1该位置已被覆盖那么我们什么都不能做直接跳到下一列j1。如果prev_state在第j位是0该位置空着必须被覆盖那么我们有两种选择横放如果j1 M且prev_state在第j1位也是0我们可以放一块横砖覆盖(i-1, j)和(i-1, j1)。这次放置没有影响到第i行的状态所以curr_state对应位不变。然后我们继续从j2开始处理。竖放我们放一块竖砖覆盖(i-1, j)和(i, j)。这意味着第i-1行的j位置被覆盖了同时第i行的j位置也被覆盖了。所以我们需要在curr_state的第j位标记为1。然后我们继续从j1开始处理。当我们扫描完所有列后必须确保prev_state中所有的0都被覆盖了即我们成功找到了一种铺法。此时产生的curr_state就是一个有效的、从prev_state转移而来的新状态。那么就有dp[i][curr_state] dp[i-1][prev_state]。这个枚举两行之间铺法的DFS是解决整个问题的核心引擎。它保证了我们既能考虑到所有可能的砖块摆放又避免了全盘搜索的冗余。最终我们想要求的是铺满前N行的方案数。我们可以想象存在第N1行并且要求第N行必须被完全铺满不能有砖头伸到第N1行。这对应着最终状态dp[N][(1M)-1]即第N行的状态是所有位都是1表示全部被覆盖没有空位需要伸到下一行。3. 核心算法实现DFS枚举与DP转移的代码级详解理论说清楚了我们来看代码如何实现。这里会给出Java版本的核心代码并逐行解释其意图和细节。我们假设棋盘规模N和M都不太大比如N, M 15这样状态总数1M是可行的最多2^15 32768种状态。首先定义一些全局变量和输入int N, M; // 棋盘的行数和列数 long[][] dp; // dp[i][state]使用long防止溢出dp数组为什么用long因为方案数可能非常大即使取模前也可能超出int范围。接下来是核心的DFS函数它负责枚举从上一行状态prev出发所有能铺满上一行并得到当前行状态now的方案。我们采用递归实现参数col表示当前处理到的列索引prev和now是当前的状态dpNext是一个临时数组用于累积下一行状态的方案数。/** * DFS枚举铺砖方式 * param col 当前处理的列索引 (0-based) * param prev 第i-1行的状态二进制位1表示已覆盖0表示待覆盖 * param now 第i行的当前状态二进制位1表示被竖砖覆盖 * param dpNext 用于累加dp[i][now]的数组 */ private static void dfs(int col, int prev, int now, long[] dpNext) { // 基准情况已经处理完所有列 if (col M) { // 当处理完所有列时prev必须全部变为1即prevfullMask表示上一行已完全铺满 // 如果prevfullMask说明我们找到了一种合法的铺设方式它导致了下一行状态为now if (prev ((1 M) - 1)) { dpNext[now] dp[currentRow][prevStartState]; // 注意这里累加的是上一行的某个状态值 // 在实际循环中prevStartState是固定的dpNext[now]会累加所有能转移到now的prev状态的方案数 // 这里为了逻辑清晰先理解dfs的作用是找到一条转移路径。 } return; } // 情况1prev的当前列已经是1被覆盖直接跳过处理下一列 if ((prev (1 col)) ! 0) { dfs(col 1, prev, now, dpNext); return; } // 情况2prev的当前列是0必须覆盖它。有两种覆盖方式。 // 方式A尝试横放砖块 (覆盖 prev行的 col 和 col1) if (col 1 M (prev (1 (col 1))) 0) { // 横放只影响prev行将prev的col和col1位都标记为1 int newPrev prev | (1 col) | (1 (col 1)); dfs(col 2, newPrev, now, dpNext); // 跳过两列 } // 方式B尝试竖放砖块 (覆盖 prev行的col 和 now行的col) // 竖放会影响两行将prev的col位标记为1同时将now的col位也标记为1 int newNow now | (1 col); int newPrev prev | (1 col); dfs(col 1, newPrev, newNow, dpNext); }重要提示上面的dfs函数是一个简化的逻辑展示它隐含了一个重要的点dp[currentRow][prevStartState]的值需要在调用前被知晓。在实际的主DP循环中我们是对每个prevStartState分别调用这个DFS来更新下一行的所有可能状态。因此更常见的写法是将DFS封装成一个“预处理”步骤或者直接在DP循环内部调用。下面我们来看主DP循环的经典写法它直接体现了“枚举上一行状态通过DFS更新下一行状态”的过程// 初始化DP数组行数为N1多一行方便处理状态数为 1M dp new long[N 1][1 M]; // 第0行的状态是全1想象第0行之上已经铺满没有任何空位需要伸到第1行 dp[0][(1 M) - 1] 1; // 遍历每一行 for (int i 0; i N; i) { // 遍历第i行的所有可能状态 for (int state 0; state (1 M); state) { if (dp[i][state] 0) continue; // 如果该状态不可达跳过 // 对于第i行的每个可达状态state枚举所有铺法得到第i1行的各种状态nextState // 这里用一个辅助数组nextDP来暂存第i1行的结果 long[] nextDP new long[1 M]; // 调用DFS从第0列开始初始时第i行状态为state需要被铺满第i1行状态为0空 dfs(0, state, 0, nextDP); // 将DFS枚举得到的所有转移方案累加到dp[i1][nextState]中 for (int nextState 0; nextState (1 M); nextState) { if (nextDP[nextState] ! 0) { dp[i 1][nextState] (dp[i 1][nextState] dp[i][state] * nextDP[nextState]) % MOD; } } } } // 最终答案铺完前N行且第N行状态为全1没有空位 long answer dp[N][(1 M) - 1];这里有几个极其关键的细节和易错点初始化dp[0][fullMask] 1这是状态的起点。它表示第0行一个虚拟的、已经铺好的行的状态是全满的只有这样我们才能开始铺第1行。这是一个边界条件的设定需要理解其物理意义。DFS中的prev和now在dfs(col, prev, now, nextDP)调用时prev参数是“当前需要被铺满的行”的状态它最初是state第i行状态。在DFS递归过程中我们通过放置砖块来修改prev目标是将其所有位变成1。now参数是“下一行”的状态初始为0在放置竖砖时我们会将now的对应位设为1。当DFS递归到底col M且prev变为全1时我们就得到了一种合法的铺法其对应的下一行状态就是最终的now。nextDP数组的作用对于固定的一个stateDFS会枚举出所有能铺满它并产生的nextState。nextDP[nextState]记录的是从这一个特定的state出发能转移到nextState的方案数。这个数通常是1因为对于固定的state每种铺法唯一确定一个nextState但在某些更复杂的砖块形状下可能大于1。所以最终转移方程是dp[i1][nextState] dp[i][state] * nextDP[nextState]。取模操作答案很大必须在每次加法后取模。注意dp[i][state]和nextDP[nextState]相乘也可能溢出需要使用long类型并在计算后取模。时间复杂度外层循环N次内层循环状态数S 1M对于每个状态都要进行一次DFS枚举。DFS枚举的时间复杂度与M相关最坏是O(2^M)其实不是因为DFS的递归树分支是常数横放或竖放其深度是M所以一次DFS是O(2^M)吗实际上由于我们通过prev的状态来剪枝遇到1就跳过枚举所有铺法的复杂度大约在O(2^{M/2})量级是一个卡特兰数相关的复杂度。总体复杂度约为O(N * S * F(M))其中F(M)是枚举铺法的复杂度。当M15时这个算法是可行的。4. 性能优化与边界处理让代码真正高效可靠基础的状压DP实现后我们还需要考虑一些优化和边界情况以确保代码在竞赛环境中既快又稳。4.1 预处理转移关系在上述循环中我们对每一行的每个状态state都调用了一次DFS来枚举转移。但仔细想想转移关系(state - nextState)只与M有关与行号i无关这意味着我们可以提前把所有可能的转移关系预处理出来存到一个列表或数组中。这样在DP主循环中就可以直接查表省去了大量重复的DFS调用。预处理可以这样实现// trans[state] 是一个列表存放所有能从state转移到的(nextState, ways)对 Listint[][] trans new List[1 M]; // ways通常为1可以只存nextState for (int s 0; s (1 M); s) { trans[s] new ArrayList(); long[] tmp new long[1 M]; dfs(0, s, 0, tmp); // 使用一个临时数组接收DFS结果 for (int ns 0; ns (1 M); ns) { if (tmp[ns] ! 0) { trans[s].add(new int[]{ns, (int)tmp[ns]}); // 存储转移到的状态和方案数 } } } // 主DP循环变为 for (int i 0; i N; i) { for (int s 0; s (1 M); s) { if (dp[i][s] 0) continue; for (int[] t : trans[s]) { int ns t[0]; int ways t[1]; dp[i1][ns] (dp[i1][ns] dp[i][s] * ways) % MOD; } } }这个优化在M较大时效果显著属于典型的“空间换时间”。4.2 处理大数取模与输入限制蓝桥杯的题目通常要求结果对某个数取模比如1000000007。我们需要在每次加法、乘法后及时取模。使用long类型存储中间结果可以避免溢出。另外要留意题目中N和M的范围。如果M N我们可以交换N和M因为覆盖方案数只与棋盘面积和形状有关与行列方向无关。并且当M较大时状态数1M会指数增长可能超出内存或时间限制。有时题目会保证N*M是偶数因为1x2砖块覆盖总面积必须是偶数这也是一个有用的剪枝条件如果N*M是奇数答案直接为0。4.3 滚动数组优化空间我们的DP数组是dp[N1][1M]。如果N很大比如几百而1M也很大比如M12状态数4096这个二维数组可能占用几百MB内存导致内存超限。观察转移方程dp[i1][next]只依赖于dp[i][prev]。因此我们可以使用滚动数组只保留两行状态。long[][] dp new long[2][1 M]; int cur 0, nxt 1; dp[cur][(1M)-1] 1; for (int i 0; i N; i) { Arrays.fill(dp[nxt], 0); // 清空下一行 for (int s 0; s (1 M); s) { if (dp[cur][s] 0) continue; for (int[] t : trans[s]) { int ns t[0]; int ways t[1]; dp[nxt][ns] (dp[nxt][ns] dp[cur][s] * ways) % MOD; } } // 交换当前行和下一行 int tmp cur; cur nxt; nxt tmp; } long answer dp[cur][(1 M) - 1]; // 注意最后一行结束后cur指向的是第N行的状态这个优化将空间复杂度从O(N * S)降到了O(S)是处理大规模N时的必备技巧。4.4 针对特定砖块形状的DFS修改我们以上讨论的都是1x2的砖块。如果砖块形状变化比如2x2的方块或者L形的三格砖俄罗斯方块里的那种核心的状压DP框架不变唯一需要修改的就是那个枚举铺法的DFS函数。你需要根据新砖块的形状设计新的放置规则。例如对于2x2方块它一次覆盖两行两列。那么在DFS枚举时当遇到prev行的一个0你可以选择放置一个2x2方块前提是prev行的j, j1位都是0并且now代表下一行的j, j1位当前也都是0因为方块会覆盖到下一行。放置后prev和now的对应四位都要标记为1。对于L形砖情况更复杂可能有多种旋转形态。你需要枚举所有可能的放置方式并确保放置后不超出边界、不重叠。这会使DFS的代码变得更复杂但原理相通都是通过递归从左到右扫描尝试用各种砖块填充prev行中的0并更新now行的状态。5. 实战演练与调试技巧从理论到AC的最后一公里理解了算法写出了代码不代表就能AC。在竞赛中调试和验证是关键一步。以下是一些实战心得1. 从小规模数据开始验证不要一上来就用N10, M10测试。先测试N1, M2答案应为1横放一块砖N2, M2答案应为2要么都横放要么都竖放。再测试N2, M3可以手工计算或搜索网上已知的经典结果多米诺覆盖 2x3 棋盘有3种方案。用这些简单案例验证你的DP和DFS逻辑是否正确。2. 打印中间状态进行调试如果结果不对可以打印出预处理后的转移关系trans。看看对于某个简单的state比如0b000它能转移到哪些nextState转移方案数是否正确。也可以打印出每一行DP结束后的dp[i]数组观察状态值的分布是否合理。3. 注意整型溢出和取模这是最隐蔽的bug来源。确保所有dp值都用long并且在dp[i][s] * ways这里即使dp[i][s]和ways都是int它们的乘积也可能超出int范围所以必须先转换成long再计算和取模。Java中两个int相乘结果还是int可能会溢出后才赋值给long变量。安全的写法是(dp[i][s] * (long)ways) % MOD。4. 处理N0或M0的边界虽然题目通常不会给出这种数据但好的习惯是加上判断。当N0 || M0时一个空棋盘铺满的方案数应该是1什么都不铺。但根据我们的DP初始化dp[0][fullMask]1如果M0那么fullMask (10)-1 0最终答案dp[N][0]也是1逻辑自洽。但为了安全可以特殊处理。5. 利用对称性剪枝高级优化对于某些对称的棋盘很多状态是等价的。例如状态0b0011和0b1100在覆盖方案数上可能是对称的。我们可以定义一个状态的最小表示比如循环左移/右移后取最小值将等价状态归并进一步减少状态数。但这属于竞赛中的高级技巧在时间紧迫的情况下优先保证基础算法的正确性更为重要。最后将完整的、经过优化的代码整合起来并处理好输入输出你就能稳稳地拿下这类“铺瓷砖”问题。记住其核心永远是状态压缩表示行覆盖情况DFS枚举两行间的所有合法填充方式利用DP按行递推累计方案数。把这个模型吃透它就从一个令人头疼的难题变成了你算法工具箱里一件趁手的兵器。 状态压缩DP精解：多米诺骨牌覆盖问题的算法实现与优化
1. 项目概述与问题引入“铺瓷砖”这个题目听起来像是装修工地的活儿但在算法竞赛的语境下尤其是像蓝桥杯国赛这个级别的舞台上它往往是一个披着生活外衣的、对动态规划DP和状态压缩技巧的深度考察。我当年第一次在模拟赛里遇到这类题目时第一反应也是“这不就是排列组合吗”结果一上手就发现状态空间大得惊人暴力搜索根本跑不完。这类问题的核心魅力在于它用一个非常直观的场景——用固定形状的瓷砖铺满一个给定大小的矩形地面——来包装一个复杂的组合数学与状态转移问题。对于Java B组的选手而言这不仅是编程能力的测试更是对思维严谨性、对问题抽象能力以及对经典算法模型灵活运用的一次综合大考。简单来说题目通常会给你一个N x M的网格地面以及一种或几种固定形状的瓷砖比如1x2的长方形砖或者更复杂的L形砖。你需要计算出恰好铺满整个地面不允许重叠不允许超出边界的所有不同铺设方案数。这个“所有不同方案数”就是最终的答案往往是一个巨大的数字需要我们对结果取模。问题的难点从来不在于理解“铺满”这个概念而在于如何高效、无遗漏且不重复地枚举所有可能的铺设状态。当N和M稍微大一点比如达到10这个量级朴素的想法如深度优先搜索DFS会立刻遇到组合爆炸时间复杂度过高。这时状态压缩动态规划状压DP就成了几乎唯一的“标准答案”。在接下来的内容里我不会仅仅给出一个AC的代码模板。那样做意义不大因为下次题目稍微变一下形你可能又不会了。我将带你彻底拆解“铺瓷砖”问题的内核从最基础的思路开始一步步推导为什么需要状压DP如何设计状态如何进行状态转移并针对Java实现中的关键细节和常见“坑点”进行重点剖析。我们会用1x2的砖块即骨牌覆盖N x M棋盘这个最经典的“多米诺骨牌覆盖”问题作为主线因为它涵盖了此类问题的所有核心思想。掌握了它再遇到L形砖、更复杂的棋盘如存在障碍物等变种你都能触类旁通。2. 从暴力搜索到状压DP思路的演进与必然性我们先从一个最直观的解法开始深度优先搜索DFS。想象我们站在棋盘的左上角尝试放置第一块砖。砖可以横着放覆盖两个水平相邻的格子也可以竖着放覆盖两个垂直相邻的格子。我们做一个选择标记这两个格子为已覆盖然后递归地去铺剩下的格子。当所有格子都被覆盖时就找到了一种方案。这个思路完全正确但为什么不行呢核心在于重复计算和状态爆炸。假设棋盘是2 x 3的用1x2的砖去铺。我们手动枚举一下就会发现某些不同的放置顺序最终得到的铺设图案可能是一样的。DFS会把这些顺序都当作不同的搜索路径导致重复计数。更致命的是随着棋盘变大搜索树的分支会呈指数级增长。对于N10, M10的棋盘格子数100即使有各种剪枝搜索空间也依然是天文数字不可能在规定时间内通常1秒完成计算。那么如何避免重复和爆炸我们需要换一个视角。不要从“当前该放哪块砖”的角度思考而是从“当前行的覆盖情况”来思考。这就是按行递推的思想。我们一行一行地铺。当铺到第i行时第i-1行及其以上的所有行必须已经被完全铺满因为砖不会悬空。此时第i行某些格子可能已经被从上一行竖着放下来的砖覆盖了剩下的格子需要我们在本行内通过横放砖块或者和下一行配合竖放砖块来覆盖。如何描述一行的“覆盖情况”我们用状态压缩。用一个M位的二进制数来表示一行中每个格子的状态。通常我们用1表示这个格子已经被覆盖可能是被上一行竖下来的砖盖住了也可能是被本行横放的砖盖住了用0表示这个格子还空着需要被覆盖。注意这个“需要被覆盖”是相对于当前决策阶段而言的。当我们决策第i行时1表示这个位置不能再放砖的起点因为已经被占了0表示这个位置必须被作为某块砖的起点来覆盖要么横放要么和下一行一起竖放。有了这个定义我们就可以设计DP状态了。设dp[i][state]表示铺完前i行并且第i行的覆盖状态为state时所有可能的方案总数。这里state就是那个M位的二进制整数它的二进制表示对应第i行每个格子的“是否已被覆盖”状态。关键转移如何从dp[i-1][prev_state]转移到dp[i][curr_state]这意味着已知第i-1行铺完后的状态是prev_state我们如何摆放砖块使得第i-1行被完全铺满即所有prev_state中的0都必须被填上并且同时决定了第i行的状态curr_state。这个过程可以通过一个DFS函数来枚举。这个DFS不是在全盘搜索而是在两行之间针对特定的prev_state枚举所有可能的砖块摆放方式并计算出每种摆放方式产生的curr_state。具体来说我们从第i-1行的最左边格子开始扫描用列索引j从0到M-1。如果prev_state在第j位是1该位置已被覆盖那么我们什么都不能做直接跳到下一列j1。如果prev_state在第j位是0该位置空着必须被覆盖那么我们有两种选择横放如果j1 M且prev_state在第j1位也是0我们可以放一块横砖覆盖(i-1, j)和(i-1, j1)。这次放置没有影响到第i行的状态所以curr_state对应位不变。然后我们继续从j2开始处理。竖放我们放一块竖砖覆盖(i-1, j)和(i, j)。这意味着第i-1行的j位置被覆盖了同时第i行的j位置也被覆盖了。所以我们需要在curr_state的第j位标记为1。然后我们继续从j1开始处理。当我们扫描完所有列后必须确保prev_state中所有的0都被覆盖了即我们成功找到了一种铺法。此时产生的curr_state就是一个有效的、从prev_state转移而来的新状态。那么就有dp[i][curr_state] dp[i-1][prev_state]。这个枚举两行之间铺法的DFS是解决整个问题的核心引擎。它保证了我们既能考虑到所有可能的砖块摆放又避免了全盘搜索的冗余。最终我们想要求的是铺满前N行的方案数。我们可以想象存在第N1行并且要求第N行必须被完全铺满不能有砖头伸到第N1行。这对应着最终状态dp[N][(1M)-1]即第N行的状态是所有位都是1表示全部被覆盖没有空位需要伸到下一行。3. 核心算法实现DFS枚举与DP转移的代码级详解理论说清楚了我们来看代码如何实现。这里会给出Java版本的核心代码并逐行解释其意图和细节。我们假设棋盘规模N和M都不太大比如N, M 15这样状态总数1M是可行的最多2^15 32768种状态。首先定义一些全局变量和输入int N, M; // 棋盘的行数和列数 long[][] dp; // dp[i][state]使用long防止溢出dp数组为什么用long因为方案数可能非常大即使取模前也可能超出int范围。接下来是核心的DFS函数它负责枚举从上一行状态prev出发所有能铺满上一行并得到当前行状态now的方案。我们采用递归实现参数col表示当前处理到的列索引prev和now是当前的状态dpNext是一个临时数组用于累积下一行状态的方案数。/** * DFS枚举铺砖方式 * param col 当前处理的列索引 (0-based) * param prev 第i-1行的状态二进制位1表示已覆盖0表示待覆盖 * param now 第i行的当前状态二进制位1表示被竖砖覆盖 * param dpNext 用于累加dp[i][now]的数组 */ private static void dfs(int col, int prev, int now, long[] dpNext) { // 基准情况已经处理完所有列 if (col M) { // 当处理完所有列时prev必须全部变为1即prevfullMask表示上一行已完全铺满 // 如果prevfullMask说明我们找到了一种合法的铺设方式它导致了下一行状态为now if (prev ((1 M) - 1)) { dpNext[now] dp[currentRow][prevStartState]; // 注意这里累加的是上一行的某个状态值 // 在实际循环中prevStartState是固定的dpNext[now]会累加所有能转移到now的prev状态的方案数 // 这里为了逻辑清晰先理解dfs的作用是找到一条转移路径。 } return; } // 情况1prev的当前列已经是1被覆盖直接跳过处理下一列 if ((prev (1 col)) ! 0) { dfs(col 1, prev, now, dpNext); return; } // 情况2prev的当前列是0必须覆盖它。有两种覆盖方式。 // 方式A尝试横放砖块 (覆盖 prev行的 col 和 col1) if (col 1 M (prev (1 (col 1))) 0) { // 横放只影响prev行将prev的col和col1位都标记为1 int newPrev prev | (1 col) | (1 (col 1)); dfs(col 2, newPrev, now, dpNext); // 跳过两列 } // 方式B尝试竖放砖块 (覆盖 prev行的col 和 now行的col) // 竖放会影响两行将prev的col位标记为1同时将now的col位也标记为1 int newNow now | (1 col); int newPrev prev | (1 col); dfs(col 1, newPrev, newNow, dpNext); }重要提示上面的dfs函数是一个简化的逻辑展示它隐含了一个重要的点dp[currentRow][prevStartState]的值需要在调用前被知晓。在实际的主DP循环中我们是对每个prevStartState分别调用这个DFS来更新下一行的所有可能状态。因此更常见的写法是将DFS封装成一个“预处理”步骤或者直接在DP循环内部调用。下面我们来看主DP循环的经典写法它直接体现了“枚举上一行状态通过DFS更新下一行状态”的过程// 初始化DP数组行数为N1多一行方便处理状态数为 1M dp new long[N 1][1 M]; // 第0行的状态是全1想象第0行之上已经铺满没有任何空位需要伸到第1行 dp[0][(1 M) - 1] 1; // 遍历每一行 for (int i 0; i N; i) { // 遍历第i行的所有可能状态 for (int state 0; state (1 M); state) { if (dp[i][state] 0) continue; // 如果该状态不可达跳过 // 对于第i行的每个可达状态state枚举所有铺法得到第i1行的各种状态nextState // 这里用一个辅助数组nextDP来暂存第i1行的结果 long[] nextDP new long[1 M]; // 调用DFS从第0列开始初始时第i行状态为state需要被铺满第i1行状态为0空 dfs(0, state, 0, nextDP); // 将DFS枚举得到的所有转移方案累加到dp[i1][nextState]中 for (int nextState 0; nextState (1 M); nextState) { if (nextDP[nextState] ! 0) { dp[i 1][nextState] (dp[i 1][nextState] dp[i][state] * nextDP[nextState]) % MOD; } } } } // 最终答案铺完前N行且第N行状态为全1没有空位 long answer dp[N][(1 M) - 1];这里有几个极其关键的细节和易错点初始化dp[0][fullMask] 1这是状态的起点。它表示第0行一个虚拟的、已经铺好的行的状态是全满的只有这样我们才能开始铺第1行。这是一个边界条件的设定需要理解其物理意义。DFS中的prev和now在dfs(col, prev, now, nextDP)调用时prev参数是“当前需要被铺满的行”的状态它最初是state第i行状态。在DFS递归过程中我们通过放置砖块来修改prev目标是将其所有位变成1。now参数是“下一行”的状态初始为0在放置竖砖时我们会将now的对应位设为1。当DFS递归到底col M且prev变为全1时我们就得到了一种合法的铺法其对应的下一行状态就是最终的now。nextDP数组的作用对于固定的一个stateDFS会枚举出所有能铺满它并产生的nextState。nextDP[nextState]记录的是从这一个特定的state出发能转移到nextState的方案数。这个数通常是1因为对于固定的state每种铺法唯一确定一个nextState但在某些更复杂的砖块形状下可能大于1。所以最终转移方程是dp[i1][nextState] dp[i][state] * nextDP[nextState]。取模操作答案很大必须在每次加法后取模。注意dp[i][state]和nextDP[nextState]相乘也可能溢出需要使用long类型并在计算后取模。时间复杂度外层循环N次内层循环状态数S 1M对于每个状态都要进行一次DFS枚举。DFS枚举的时间复杂度与M相关最坏是O(2^M)其实不是因为DFS的递归树分支是常数横放或竖放其深度是M所以一次DFS是O(2^M)吗实际上由于我们通过prev的状态来剪枝遇到1就跳过枚举所有铺法的复杂度大约在O(2^{M/2})量级是一个卡特兰数相关的复杂度。总体复杂度约为O(N * S * F(M))其中F(M)是枚举铺法的复杂度。当M15时这个算法是可行的。4. 性能优化与边界处理让代码真正高效可靠基础的状压DP实现后我们还需要考虑一些优化和边界情况以确保代码在竞赛环境中既快又稳。4.1 预处理转移关系在上述循环中我们对每一行的每个状态state都调用了一次DFS来枚举转移。但仔细想想转移关系(state - nextState)只与M有关与行号i无关这意味着我们可以提前把所有可能的转移关系预处理出来存到一个列表或数组中。这样在DP主循环中就可以直接查表省去了大量重复的DFS调用。预处理可以这样实现// trans[state] 是一个列表存放所有能从state转移到的(nextState, ways)对 Listint[][] trans new List[1 M]; // ways通常为1可以只存nextState for (int s 0; s (1 M); s) { trans[s] new ArrayList(); long[] tmp new long[1 M]; dfs(0, s, 0, tmp); // 使用一个临时数组接收DFS结果 for (int ns 0; ns (1 M); ns) { if (tmp[ns] ! 0) { trans[s].add(new int[]{ns, (int)tmp[ns]}); // 存储转移到的状态和方案数 } } } // 主DP循环变为 for (int i 0; i N; i) { for (int s 0; s (1 M); s) { if (dp[i][s] 0) continue; for (int[] t : trans[s]) { int ns t[0]; int ways t[1]; dp[i1][ns] (dp[i1][ns] dp[i][s] * ways) % MOD; } } }这个优化在M较大时效果显著属于典型的“空间换时间”。4.2 处理大数取模与输入限制蓝桥杯的题目通常要求结果对某个数取模比如1000000007。我们需要在每次加法、乘法后及时取模。使用long类型存储中间结果可以避免溢出。另外要留意题目中N和M的范围。如果M N我们可以交换N和M因为覆盖方案数只与棋盘面积和形状有关与行列方向无关。并且当M较大时状态数1M会指数增长可能超出内存或时间限制。有时题目会保证N*M是偶数因为1x2砖块覆盖总面积必须是偶数这也是一个有用的剪枝条件如果N*M是奇数答案直接为0。4.3 滚动数组优化空间我们的DP数组是dp[N1][1M]。如果N很大比如几百而1M也很大比如M12状态数4096这个二维数组可能占用几百MB内存导致内存超限。观察转移方程dp[i1][next]只依赖于dp[i][prev]。因此我们可以使用滚动数组只保留两行状态。long[][] dp new long[2][1 M]; int cur 0, nxt 1; dp[cur][(1M)-1] 1; for (int i 0; i N; i) { Arrays.fill(dp[nxt], 0); // 清空下一行 for (int s 0; s (1 M); s) { if (dp[cur][s] 0) continue; for (int[] t : trans[s]) { int ns t[0]; int ways t[1]; dp[nxt][ns] (dp[nxt][ns] dp[cur][s] * ways) % MOD; } } // 交换当前行和下一行 int tmp cur; cur nxt; nxt tmp; } long answer dp[cur][(1 M) - 1]; // 注意最后一行结束后cur指向的是第N行的状态这个优化将空间复杂度从O(N * S)降到了O(S)是处理大规模N时的必备技巧。4.4 针对特定砖块形状的DFS修改我们以上讨论的都是1x2的砖块。如果砖块形状变化比如2x2的方块或者L形的三格砖俄罗斯方块里的那种核心的状压DP框架不变唯一需要修改的就是那个枚举铺法的DFS函数。你需要根据新砖块的形状设计新的放置规则。例如对于2x2方块它一次覆盖两行两列。那么在DFS枚举时当遇到prev行的一个0你可以选择放置一个2x2方块前提是prev行的j, j1位都是0并且now代表下一行的j, j1位当前也都是0因为方块会覆盖到下一行。放置后prev和now的对应四位都要标记为1。对于L形砖情况更复杂可能有多种旋转形态。你需要枚举所有可能的放置方式并确保放置后不超出边界、不重叠。这会使DFS的代码变得更复杂但原理相通都是通过递归从左到右扫描尝试用各种砖块填充prev行中的0并更新now行的状态。5. 实战演练与调试技巧从理论到AC的最后一公里理解了算法写出了代码不代表就能AC。在竞赛中调试和验证是关键一步。以下是一些实战心得1. 从小规模数据开始验证不要一上来就用N10, M10测试。先测试N1, M2答案应为1横放一块砖N2, M2答案应为2要么都横放要么都竖放。再测试N2, M3可以手工计算或搜索网上已知的经典结果多米诺覆盖 2x3 棋盘有3种方案。用这些简单案例验证你的DP和DFS逻辑是否正确。2. 打印中间状态进行调试如果结果不对可以打印出预处理后的转移关系trans。看看对于某个简单的state比如0b000它能转移到哪些nextState转移方案数是否正确。也可以打印出每一行DP结束后的dp[i]数组观察状态值的分布是否合理。3. 注意整型溢出和取模这是最隐蔽的bug来源。确保所有dp值都用long并且在dp[i][s] * ways这里即使dp[i][s]和ways都是int它们的乘积也可能超出int范围所以必须先转换成long再计算和取模。Java中两个int相乘结果还是int可能会溢出后才赋值给long变量。安全的写法是(dp[i][s] * (long)ways) % MOD。4. 处理N0或M0的边界虽然题目通常不会给出这种数据但好的习惯是加上判断。当N0 || M0时一个空棋盘铺满的方案数应该是1什么都不铺。但根据我们的DP初始化dp[0][fullMask]1如果M0那么fullMask (10)-1 0最终答案dp[N][0]也是1逻辑自洽。但为了安全可以特殊处理。5. 利用对称性剪枝高级优化对于某些对称的棋盘很多状态是等价的。例如状态0b0011和0b1100在覆盖方案数上可能是对称的。我们可以定义一个状态的最小表示比如循环左移/右移后取最小值将等价状态归并进一步减少状态数。但这属于竞赛中的高级技巧在时间紧迫的情况下优先保证基础算法的正确性更为重要。最后将完整的、经过优化的代码整合起来并处理好输入输出你就能稳稳地拿下这类“铺瓷砖”问题。记住其核心永远是状态压缩表示行覆盖情况DFS枚举两行间的所有合法填充方式利用DP按行递推累计方案数。把这个模型吃透它就从一个令人头疼的难题变成了你算法工具箱里一件趁手的兵器。