1. 项目概述从一道国赛题看状态压缩动态规划“铺瓷砖”这个题目乍一看像是装修工地的活儿但在算法竞赛的语境里尤其是蓝桥杯国赛这个级别它立刻变成了一块检验选手对“状态压缩动态规划”理解深度的试金石。这道题通常出现在决赛阶段意味着它已经脱离了基础语法和简单数据结构的考察直指算法设计与优化的核心能力。我当年第一次在模拟赛里遇到它时也是挠头半天感觉状态千头万绪无从下手。但一旦你掌握了其背后的核心思想——状态压缩你会发现它其实是一类非常经典且“套路”清晰的问题。这类问题不仅频繁出现在蓝桥杯、ACM-ICPC等赛事中其思想在解决某些棋盘覆盖、资源调度乃至电路布局等实际工程问题时也有着异曲同工之妙。简单来说题目会给你一个固定大小的矩形区域比如 N 行 M 列以及若干种形状的瓷砖最常见的是 1x2 的矩形砖也就是多米诺骨牌要求你用这些瓷砖恰好铺满整个区域计算一共有多少种不同的铺设方案。旋转、翻转通常视为不同的方案。这里的“恰好铺满”和“所有方案数”就是动态规划DP的典型特征而“每一行的铺设状态”如何表示就是状态压缩技术大显身手的地方。2. 核心思路拆解为什么是状态压缩DP面对一个 N x M 的网格最暴力的想法是回溯搜索枚举每一格铺砖的所有可能性。但稍微计算一下就知道不可行格子数稍多比如10x10状态空间就爆炸了。动态规划是优化这类计数问题的利器其关键在于找到合适的“状态”定义和状态转移方程。2.1 状态定义的困境与突破我们本能地会想用dp[i][j]表示铺到第i行第j列时的方案数。但问题立刻来了砖块是横着铺占两列或竖着铺占两行。当你决定在(i, j)铺一块横砖时它会影响(i, j1)铺竖砖则会影响(i1, j)。这意味着当前格子的决策严重依赖于后面格子的状态简单的线性DP难以处理这种后效性。一个关键的思路转变是按行进行DP。我们不再一格一格地推进而是一行一行地铺。定义dp[i][s]表示已经铺完前i-1行并且第i行的铺设状态为s时总共的方案数。这里的“状态s”就是一个压缩的表示。2.2 状态压缩的精髓什么是“第i行的状态”想象一下第i行有 M 个格子。每个格子只有两种可能被铺满来自上一行延伸下来的竖砖的“下半部分”或者空着等待本行或下一行的砖来铺。我们用二进制位来表示1 表示该格子已经被铺了是竖砖的下半部分0 表示该格子还空着。例如M4时状态s5(二进制 0101) 表示第 i 行的第1、3列从0或1开始计数依个人习惯的格子已经被上一行的竖砖“占用了”而第2、4列是空的。这样一个s就是一个 0 到(1M)-1之间的整数完美地用一个小整数编码了一整行的格子占用情况。这就是“状态压缩”——将一行 M 个格子的布尔状态压缩成一个整数。2.3 状态转移的逻辑有了dp[i][s]如何转移到dp[i1][t]呢这代表了从第 i 行状态 s 铺到第 i1 行状态 t 的过程。这个过程可以分解为两步填充本行剩余空位状态 s 中的 0 表示本行第 i 行的空位。这些空位必须由从本行开始的砖来铺满因为下一行的砖够不到它们。铺砖有两种选择铺横砖覆盖两个连续的 0。这会将这两个 0 变成 1表示已铺但注意这个“1”是铺砖的结果不是来自上一行的占用。为了区分我们在填充过程中可以用另一个变量来表示填充后的状态。铺竖砖覆盖一个 0。竖砖的下半部分在本行上半部分在下一行。所以铺一个竖砖意味着把本行的这个 0 变成 1已铺同时在下一行的对应位置产生一个 1被占用。这个“下一行的1”正好对应了下一行状态 t 中的某个位为1。生成下一行状态在填充完本行所有空位后本行所有格子都应该是 1已铺。此时那些因为竖砖而产生的、对下一行的“占用标记”就构成了下一行的初始状态 t。换句话说t 的二进制表示中所有为 1 的位都对应着从第 i 行“长上来”的竖砖的上半部分。因此状态转移就是枚举所有能从状态 s 出发通过铺砖横砖和竖砖使得本行被完全铺满并且同时生成下一行状态 t 的所有合法方式。每找到一种方式就将dp[i][s]的方案数加到dp[i1][t]上。注意这里有一个非常重要的预处理技巧。我们并不需要在DP过程中实时计算从 s 到 t 的转移。因为行宽 M 是固定的所有可能的 s 和 t 也是有限的最多 2^M 种。我们可以预先计算出所有合法的(s, t)转移对。这个预处理过程本身也是一个深度优先搜索DFS以当前行状态 s 和下一行状态 t初始为0为起点逐列扫描根据 s 当前位是1还是0决定如何铺砖并更新 t。3. 算法实现细节与代码解析理解了核心思想后我们来看具体的代码实现。这里以最经典的 1x2 砖块铺满 N x M 地面为例其中 M 通常较小因为状态数是 2^MN 可以较大。3.1 预处理生成所有状态转移这是整个算法中最精妙也最容易出错的部分。我们写一个 DFS 函数参数是当前列索引col、当前行状态s、下一行状态t。s是已知的表示上一行留给本行的占用情况。我们在函数中试图铺满本行并生成t。从第0列开始逐列处理。/** * 预处理所有合法的状态转移 * param M 列数 * return 一个列表下标为 s值为所有能从 s 转移到的 t 的集合 */ ListInteger[] preprocess(int M) { int stateCount 1 M; // 状态总数 ListInteger[] transfer new ArrayList[stateCount]; for (int i 0; i stateCount; i) { transfer[i] new ArrayList(); } for (int s 0; s stateCount; s) { dfs(s, 0, 0, M, transfer); } return transfer; } /** * DFS深搜寻找从状态s出发的所有合法下一行状态t * param s 当前行状态 * param col 当前处理到的列 (0-indexed) * param t 正在构建的下一行状态 * param M 总列数 * param transfer 状态转移表 */ void dfs(int s, int col, int t, int M, ListInteger[] transfer) { if (col M) { // 已经处理完所有列本行必须被完全铺满即s中所有位在过程中都被处理成了1的等价形式 // 实际上我们的递归逻辑保证了当colM时s的所有空位已被铺满。 // 此时生成的t就是一个合法的下一行状态。 transfer[s].add(t); return; } // 情况1s在当前列是1被上一行竖砖占用 if ((s (1 col)) ! 0) { // 这个位置已经被占了不能放砖直接跳到下一列 // 注意t的当前列保持为0因为这里没有新的竖砖开始 dfs(s, col 1, t, M, transfer); } else { // 情况2s在当前列是0空位必须用砖铺满 // 选项2.1尝试铺横砖1x2需要当前列和下一列都是空位 if (col 1 M (s (1 (col 1))) 0) { // 横砖覆盖了col和col1列这两列在本行都被铺满对下一行t没有影响 dfs(s, col 2, t, M, transfer); } // 选项2.2尝试铺竖砖2x1 // 竖砖覆盖本行col列和下一行col列。本行col被铺满下一行col列被标记为占用t中对应位设为1 dfs(s, col 1, t | (1 col), M, transfer); } }这个 DFS 函数需要仔细理解参数s是固定的我们通过递归尝试所有铺砖方式。当col M时意味着我们已经成功用砖或跳过被占位处理完了本行所有列此时构建出的t就是一个合法的、从s能转移到的下一行状态。3.2 动态规划主过程预处理得到转移表后DP过程就非常清晰了。long solve(int N, int M) { // 确保M不大于N否则交换因为状态数是2^M我们希望M更小 if ((N 1) 1 (M 1) 1) { // 如果N和M都是奇数面积是奇数不可能用1x2砖铺满 return 0; } if (N M) { // 交换使得M是较小的那个维度 int temp N; N M; M temp; } int stateCount 1 M; ListInteger[] transfer preprocess(M); // dp[i][s]: 铺完前i行且第i行状态为s的方案数 long[][] dp new long[N 1][stateCount]; // 初始化第0行虚拟行的状态必须是“全部被占满”因为没有任何砖从上一行伸过来。 // 对于第0行我们认为它已经被完全铺满没有任何空位需要本行砖来铺其状态就是0没有竖砖的上半部分。 // 但更准确地说我们考虑铺第1行时依赖于第0行的状态。第0行作为起点应该是一个“已经被完美铺完且没有砖头伸出来”的状态。 // 这个状态就是 s0。所以 dp[0][0] 1。 dp[0][0] 1; for (int i 0; i N; i) { for (int s 0; s stateCount; s) { if (dp[i][s] 0) continue; // 剪枝 // 遍历所有能从s转移到的状态t for (int t : transfer[s]) { dp[i 1][t] dp[i][s]; } } } // 最终铺完第N行后不应该再有砖头伸向第N1行。 // 也就是说第N行的状态必须是0没有未完成的竖砖。 return dp[N][0]; }关键点提示初始化dp[0][0]1表示一种“空”的初始状态。最终答案dp[N][0]要求最后一行状态为0确保了所有砖块都完整地铺在N行之内没有超出边界。3.3 大数处理与性能优化对于较大的 N 和 M比如 M10N100方案数可能非常巨大通常会要求输出结果对某个大数如1e97取模。我们只需在累加时进行取模运算即可dp[i1][t] (dp[i1][t] dp[i][s]) % MOD。此外如果 N 特别大比如 10^9而 M 很小比如 10我们可以利用矩阵快速幂来加速。因为状态转移方程dp[i1][t] Σ dp[i][s] * A[s][t]本质上是一个线性递推其中A是状态转移矩阵A[s][t]1表示可从 s 转移到 t。那么dp[N] dp[0] * (A)^N。用矩阵快速幂可以在O((2^M)^3 * logN)时间内解决这对于 N 巨大而 M 小的情况是可行的。不过在蓝桥杯国赛环境下N 通常不会大到需要矩阵快速幂掌握基础的状压DP足以应对。4. 从解题到举一反三状态压缩DP的常见变体“铺瓷砖”是状压DP的入门经典题。一旦掌握你可以解决一系列类似问题4.1 变体一砖块形状变化题目可能将 1x2 砖块换成 1x3、L形砖俄罗斯方块等。处理思路不变但 DFS 预处理函数中的“铺砖”选项需要改变。你需要根据新砖块的形状修改递归分支。例如对于 1x3 砖你需要检查连续三列是否为空对于 L 形砖你需要枚举其所有旋转形态并检查对应格子是否为空。4.2 变体二棋盘限制有些格子可能被禁止铺设比如坏了。这可以在状态s中融入进来。一种方法是将棋盘障碍也视为一种“预先占用”在预处理 DFS 时如果当前列是障碍格那么即使s对应位是0也不能铺砖只能跳过如果障碍格在s中对应位是1那本身就是矛盾的该状态无效。更常见的是将障碍信息作为参数传入DFS在递归时判断。4.3 变体三求具体方案或最优解原题是计数问题。如果改为输出一种具体方案需要在DP过程中记录路径即从哪个状态转移而来。如果改为求最优解比如每种砖有成本求最小总成本那么将 DP 数组的值从方案数改为最小成本状态转移时的加法改为取最小值即可。4.4 与其他模型的结合状压DP的思想可以迁移到很多其他问题例如旅行商问题TSPdp[s][i]表示已访问城市集合为s压缩状态当前位于城市i的最短路径。任务调度dp[s]表示完成任务集合s的最短时间或最大收益。棋盘覆盖/炮兵阵地和铺瓷砖高度相似只是摆放规则和状态定义略有不同。5. 实战调试与常见“坑点”即使理解了算法实现时也难免踩坑。下面是我在多次练习和教学中总结的几个常见问题5.1 初始化与最终状态理解错误这是最容易出错的地方。dp[0][0] 1的物理意义是第0行是虚拟的、已经铺好的行并且没有任何砖块伸到第1行。最终状态dp[N][0]表示第N行铺完后也没有砖块伸向不存在的第N1行。一定要想清楚这个“行”的索引含义。有些人会定义dp[i][s]为铺完前 i 行后第 i 行的状态这时 i 从1开始初始化dp[0][0]1可能就更直观。5.2 DFS预处理中的位运算错误在DFS中检查s的第col位是否为1用的是(s (1 col)) ! 0。设置t的第col位为1用的是t | (1 col)。务必注意运算符的优先级不确定时就加括号。例如s (1 col) 0在Java中是错误的因为优先级高于必须写成(s (1 col)) 0。5.3 横砖放置的边界检查在尝试铺横砖时一定要检查col 1 M否则会数组越界。这是递归中的一个边界条件容易遗漏。5.4 状态空间过大与内存优化当 M10 时状态数有1024个DP数组是dp[N1][1024]对于 N100 是可行的。但如果 M 更大比如12状态数4096可能就需要考虑优化。一种常见的优化是“滚动数组”因为dp[i1]只依赖于dp[i]所以只需要两个一维数组交替使用即可能将空间复杂度从 O(N * 2^M) 降到 O(2^M)。long[] current new long[stateCount]; long[] next new long[stateCount]; current[0] 1; for (int i 0; i N; i) { Arrays.fill(next, 0); // 清空next数组 for (int s 0; s stateCount; s) { if (current[s] 0) continue; for (int t : transfer[s]) { next[t] (next[t] current[s]) % MOD; } } // 交换数组准备下一次迭代 long[] temp current; current next; next temp; } return current[0]; // 最终状态在current数组中5.5 整数溢出问题方案数增长极快即使 N 和 M 不大结果也可能超出long的范围2^63-1。务必在比赛时看清题目要求如果要求取模从一开始就进行取模运算。如果题目不要求取模且结果可能很大可能需要使用BigInteger但这在算法竞赛中非常罕见通常都会要求取模。6. 性能分析与竞赛策略在蓝桥杯等竞赛中遇到此类题目可以遵循以下步骤识别模型看到网格覆盖、计数、数据范围N大M小立刻联想到状压DP。确定状态定义dp[i][s]其中 s 是当前行状态。预处理转移编写 DFS 函数生成所有合法的(s, t)对。这是核心写完后可以用小数据如M2,3手动验证。DP循环初始化dp[0][0]1循环 N 次根据转移表更新。输出答案dp[N][0]。时间复杂度为O(N * 2^M * T)其中 T 是平均每个状态 s 能转移到的状态 t 的数量。由于有效的转移并不多这个复杂度对于 M10, N100 是绰绰有余的。最后再分享一个调试小技巧当你的程序输出结果不对时不要急于看代码。先尝试 N1, M1,2,3 等极小情况手动计算答案然后与程序输出对比。往往能快速定位是预处理错误还是DP循环错误。对于状压DP画图是理解状态转移的最好帮手在纸上画出一个 N2, M3 的网格手动模拟一下 DFS 和 DP 的过程比干看代码有效得多。这道题吃透后你会对“状态”和“压缩”有更深的理解再遇到类似的题目思路就会清晰很多。 
长河君 · 2026/8/29 6:22:35 · 阅读 1.2k 状态压缩动态规划精解：从铺瓷砖问题到算法竞赛实战
1. 项目概述从一道国赛题看状态压缩动态规划“铺瓷砖”这个题目乍一看像是装修工地的活儿但在算法竞赛的语境里尤其是蓝桥杯国赛这个级别它立刻变成了一块检验选手对“状态压缩动态规划”理解深度的试金石。这道题通常出现在决赛阶段意味着它已经脱离了基础语法和简单数据结构的考察直指算法设计与优化的核心能力。我当年第一次在模拟赛里遇到它时也是挠头半天感觉状态千头万绪无从下手。但一旦你掌握了其背后的核心思想——状态压缩你会发现它其实是一类非常经典且“套路”清晰的问题。这类问题不仅频繁出现在蓝桥杯、ACM-ICPC等赛事中其思想在解决某些棋盘覆盖、资源调度乃至电路布局等实际工程问题时也有着异曲同工之妙。简单来说题目会给你一个固定大小的矩形区域比如 N 行 M 列以及若干种形状的瓷砖最常见的是 1x2 的矩形砖也就是多米诺骨牌要求你用这些瓷砖恰好铺满整个区域计算一共有多少种不同的铺设方案。旋转、翻转通常视为不同的方案。这里的“恰好铺满”和“所有方案数”就是动态规划DP的典型特征而“每一行的铺设状态”如何表示就是状态压缩技术大显身手的地方。2. 核心思路拆解为什么是状态压缩DP面对一个 N x M 的网格最暴力的想法是回溯搜索枚举每一格铺砖的所有可能性。但稍微计算一下就知道不可行格子数稍多比如10x10状态空间就爆炸了。动态规划是优化这类计数问题的利器其关键在于找到合适的“状态”定义和状态转移方程。2.1 状态定义的困境与突破我们本能地会想用dp[i][j]表示铺到第i行第j列时的方案数。但问题立刻来了砖块是横着铺占两列或竖着铺占两行。当你决定在(i, j)铺一块横砖时它会影响(i, j1)铺竖砖则会影响(i1, j)。这意味着当前格子的决策严重依赖于后面格子的状态简单的线性DP难以处理这种后效性。一个关键的思路转变是按行进行DP。我们不再一格一格地推进而是一行一行地铺。定义dp[i][s]表示已经铺完前i-1行并且第i行的铺设状态为s时总共的方案数。这里的“状态s”就是一个压缩的表示。2.2 状态压缩的精髓什么是“第i行的状态”想象一下第i行有 M 个格子。每个格子只有两种可能被铺满来自上一行延伸下来的竖砖的“下半部分”或者空着等待本行或下一行的砖来铺。我们用二进制位来表示1 表示该格子已经被铺了是竖砖的下半部分0 表示该格子还空着。例如M4时状态s5(二进制 0101) 表示第 i 行的第1、3列从0或1开始计数依个人习惯的格子已经被上一行的竖砖“占用了”而第2、4列是空的。这样一个s就是一个 0 到(1M)-1之间的整数完美地用一个小整数编码了一整行的格子占用情况。这就是“状态压缩”——将一行 M 个格子的布尔状态压缩成一个整数。2.3 状态转移的逻辑有了dp[i][s]如何转移到dp[i1][t]呢这代表了从第 i 行状态 s 铺到第 i1 行状态 t 的过程。这个过程可以分解为两步填充本行剩余空位状态 s 中的 0 表示本行第 i 行的空位。这些空位必须由从本行开始的砖来铺满因为下一行的砖够不到它们。铺砖有两种选择铺横砖覆盖两个连续的 0。这会将这两个 0 变成 1表示已铺但注意这个“1”是铺砖的结果不是来自上一行的占用。为了区分我们在填充过程中可以用另一个变量来表示填充后的状态。铺竖砖覆盖一个 0。竖砖的下半部分在本行上半部分在下一行。所以铺一个竖砖意味着把本行的这个 0 变成 1已铺同时在下一行的对应位置产生一个 1被占用。这个“下一行的1”正好对应了下一行状态 t 中的某个位为1。生成下一行状态在填充完本行所有空位后本行所有格子都应该是 1已铺。此时那些因为竖砖而产生的、对下一行的“占用标记”就构成了下一行的初始状态 t。换句话说t 的二进制表示中所有为 1 的位都对应着从第 i 行“长上来”的竖砖的上半部分。因此状态转移就是枚举所有能从状态 s 出发通过铺砖横砖和竖砖使得本行被完全铺满并且同时生成下一行状态 t 的所有合法方式。每找到一种方式就将dp[i][s]的方案数加到dp[i1][t]上。注意这里有一个非常重要的预处理技巧。我们并不需要在DP过程中实时计算从 s 到 t 的转移。因为行宽 M 是固定的所有可能的 s 和 t 也是有限的最多 2^M 种。我们可以预先计算出所有合法的(s, t)转移对。这个预处理过程本身也是一个深度优先搜索DFS以当前行状态 s 和下一行状态 t初始为0为起点逐列扫描根据 s 当前位是1还是0决定如何铺砖并更新 t。3. 算法实现细节与代码解析理解了核心思想后我们来看具体的代码实现。这里以最经典的 1x2 砖块铺满 N x M 地面为例其中 M 通常较小因为状态数是 2^MN 可以较大。3.1 预处理生成所有状态转移这是整个算法中最精妙也最容易出错的部分。我们写一个 DFS 函数参数是当前列索引col、当前行状态s、下一行状态t。s是已知的表示上一行留给本行的占用情况。我们在函数中试图铺满本行并生成t。从第0列开始逐列处理。/** * 预处理所有合法的状态转移 * param M 列数 * return 一个列表下标为 s值为所有能从 s 转移到的 t 的集合 */ ListInteger[] preprocess(int M) { int stateCount 1 M; // 状态总数 ListInteger[] transfer new ArrayList[stateCount]; for (int i 0; i stateCount; i) { transfer[i] new ArrayList(); } for (int s 0; s stateCount; s) { dfs(s, 0, 0, M, transfer); } return transfer; } /** * DFS深搜寻找从状态s出发的所有合法下一行状态t * param s 当前行状态 * param col 当前处理到的列 (0-indexed) * param t 正在构建的下一行状态 * param M 总列数 * param transfer 状态转移表 */ void dfs(int s, int col, int t, int M, ListInteger[] transfer) { if (col M) { // 已经处理完所有列本行必须被完全铺满即s中所有位在过程中都被处理成了1的等价形式 // 实际上我们的递归逻辑保证了当colM时s的所有空位已被铺满。 // 此时生成的t就是一个合法的下一行状态。 transfer[s].add(t); return; } // 情况1s在当前列是1被上一行竖砖占用 if ((s (1 col)) ! 0) { // 这个位置已经被占了不能放砖直接跳到下一列 // 注意t的当前列保持为0因为这里没有新的竖砖开始 dfs(s, col 1, t, M, transfer); } else { // 情况2s在当前列是0空位必须用砖铺满 // 选项2.1尝试铺横砖1x2需要当前列和下一列都是空位 if (col 1 M (s (1 (col 1))) 0) { // 横砖覆盖了col和col1列这两列在本行都被铺满对下一行t没有影响 dfs(s, col 2, t, M, transfer); } // 选项2.2尝试铺竖砖2x1 // 竖砖覆盖本行col列和下一行col列。本行col被铺满下一行col列被标记为占用t中对应位设为1 dfs(s, col 1, t | (1 col), M, transfer); } }这个 DFS 函数需要仔细理解参数s是固定的我们通过递归尝试所有铺砖方式。当col M时意味着我们已经成功用砖或跳过被占位处理完了本行所有列此时构建出的t就是一个合法的、从s能转移到的下一行状态。3.2 动态规划主过程预处理得到转移表后DP过程就非常清晰了。long solve(int N, int M) { // 确保M不大于N否则交换因为状态数是2^M我们希望M更小 if ((N 1) 1 (M 1) 1) { // 如果N和M都是奇数面积是奇数不可能用1x2砖铺满 return 0; } if (N M) { // 交换使得M是较小的那个维度 int temp N; N M; M temp; } int stateCount 1 M; ListInteger[] transfer preprocess(M); // dp[i][s]: 铺完前i行且第i行状态为s的方案数 long[][] dp new long[N 1][stateCount]; // 初始化第0行虚拟行的状态必须是“全部被占满”因为没有任何砖从上一行伸过来。 // 对于第0行我们认为它已经被完全铺满没有任何空位需要本行砖来铺其状态就是0没有竖砖的上半部分。 // 但更准确地说我们考虑铺第1行时依赖于第0行的状态。第0行作为起点应该是一个“已经被完美铺完且没有砖头伸出来”的状态。 // 这个状态就是 s0。所以 dp[0][0] 1。 dp[0][0] 1; for (int i 0; i N; i) { for (int s 0; s stateCount; s) { if (dp[i][s] 0) continue; // 剪枝 // 遍历所有能从s转移到的状态t for (int t : transfer[s]) { dp[i 1][t] dp[i][s]; } } } // 最终铺完第N行后不应该再有砖头伸向第N1行。 // 也就是说第N行的状态必须是0没有未完成的竖砖。 return dp[N][0]; }关键点提示初始化dp[0][0]1表示一种“空”的初始状态。最终答案dp[N][0]要求最后一行状态为0确保了所有砖块都完整地铺在N行之内没有超出边界。3.3 大数处理与性能优化对于较大的 N 和 M比如 M10N100方案数可能非常巨大通常会要求输出结果对某个大数如1e97取模。我们只需在累加时进行取模运算即可dp[i1][t] (dp[i1][t] dp[i][s]) % MOD。此外如果 N 特别大比如 10^9而 M 很小比如 10我们可以利用矩阵快速幂来加速。因为状态转移方程dp[i1][t] Σ dp[i][s] * A[s][t]本质上是一个线性递推其中A是状态转移矩阵A[s][t]1表示可从 s 转移到 t。那么dp[N] dp[0] * (A)^N。用矩阵快速幂可以在O((2^M)^3 * logN)时间内解决这对于 N 巨大而 M 小的情况是可行的。不过在蓝桥杯国赛环境下N 通常不会大到需要矩阵快速幂掌握基础的状压DP足以应对。4. 从解题到举一反三状态压缩DP的常见变体“铺瓷砖”是状压DP的入门经典题。一旦掌握你可以解决一系列类似问题4.1 变体一砖块形状变化题目可能将 1x2 砖块换成 1x3、L形砖俄罗斯方块等。处理思路不变但 DFS 预处理函数中的“铺砖”选项需要改变。你需要根据新砖块的形状修改递归分支。例如对于 1x3 砖你需要检查连续三列是否为空对于 L 形砖你需要枚举其所有旋转形态并检查对应格子是否为空。4.2 变体二棋盘限制有些格子可能被禁止铺设比如坏了。这可以在状态s中融入进来。一种方法是将棋盘障碍也视为一种“预先占用”在预处理 DFS 时如果当前列是障碍格那么即使s对应位是0也不能铺砖只能跳过如果障碍格在s中对应位是1那本身就是矛盾的该状态无效。更常见的是将障碍信息作为参数传入DFS在递归时判断。4.3 变体三求具体方案或最优解原题是计数问题。如果改为输出一种具体方案需要在DP过程中记录路径即从哪个状态转移而来。如果改为求最优解比如每种砖有成本求最小总成本那么将 DP 数组的值从方案数改为最小成本状态转移时的加法改为取最小值即可。4.4 与其他模型的结合状压DP的思想可以迁移到很多其他问题例如旅行商问题TSPdp[s][i]表示已访问城市集合为s压缩状态当前位于城市i的最短路径。任务调度dp[s]表示完成任务集合s的最短时间或最大收益。棋盘覆盖/炮兵阵地和铺瓷砖高度相似只是摆放规则和状态定义略有不同。5. 实战调试与常见“坑点”即使理解了算法实现时也难免踩坑。下面是我在多次练习和教学中总结的几个常见问题5.1 初始化与最终状态理解错误这是最容易出错的地方。dp[0][0] 1的物理意义是第0行是虚拟的、已经铺好的行并且没有任何砖块伸到第1行。最终状态dp[N][0]表示第N行铺完后也没有砖块伸向不存在的第N1行。一定要想清楚这个“行”的索引含义。有些人会定义dp[i][s]为铺完前 i 行后第 i 行的状态这时 i 从1开始初始化dp[0][0]1可能就更直观。5.2 DFS预处理中的位运算错误在DFS中检查s的第col位是否为1用的是(s (1 col)) ! 0。设置t的第col位为1用的是t | (1 col)。务必注意运算符的优先级不确定时就加括号。例如s (1 col) 0在Java中是错误的因为优先级高于必须写成(s (1 col)) 0。5.3 横砖放置的边界检查在尝试铺横砖时一定要检查col 1 M否则会数组越界。这是递归中的一个边界条件容易遗漏。5.4 状态空间过大与内存优化当 M10 时状态数有1024个DP数组是dp[N1][1024]对于 N100 是可行的。但如果 M 更大比如12状态数4096可能就需要考虑优化。一种常见的优化是“滚动数组”因为dp[i1]只依赖于dp[i]所以只需要两个一维数组交替使用即可能将空间复杂度从 O(N * 2^M) 降到 O(2^M)。long[] current new long[stateCount]; long[] next new long[stateCount]; current[0] 1; for (int i 0; i N; i) { Arrays.fill(next, 0); // 清空next数组 for (int s 0; s stateCount; s) { if (current[s] 0) continue; for (int t : transfer[s]) { next[t] (next[t] current[s]) % MOD; } } // 交换数组准备下一次迭代 long[] temp current; current next; next temp; } return current[0]; // 最终状态在current数组中5.5 整数溢出问题方案数增长极快即使 N 和 M 不大结果也可能超出long的范围2^63-1。务必在比赛时看清题目要求如果要求取模从一开始就进行取模运算。如果题目不要求取模且结果可能很大可能需要使用BigInteger但这在算法竞赛中非常罕见通常都会要求取模。6. 性能分析与竞赛策略在蓝桥杯等竞赛中遇到此类题目可以遵循以下步骤识别模型看到网格覆盖、计数、数据范围N大M小立刻联想到状压DP。确定状态定义dp[i][s]其中 s 是当前行状态。预处理转移编写 DFS 函数生成所有合法的(s, t)对。这是核心写完后可以用小数据如M2,3手动验证。DP循环初始化dp[0][0]1循环 N 次根据转移表更新。输出答案dp[N][0]。时间复杂度为O(N * 2^M * T)其中 T 是平均每个状态 s 能转移到的状态 t 的数量。由于有效的转移并不多这个复杂度对于 M10, N100 是绰绰有余的。最后再分享一个调试小技巧当你的程序输出结果不对时不要急于看代码。先尝试 N1, M1,2,3 等极小情况手动计算答案然后与程序输出对比。往往能快速定位是预处理错误还是DP循环错误。对于状压DP画图是理解状态转移的最好帮手在纸上画出一个 N2, M3 的网格手动模拟一下 DFS 和 DP 的过程比干看代码有效得多。这道题吃透后你会对“状态”和“压缩”有更深的理解再遇到类似的题目思路就会清晰很多。