2026/8/28 21:53:23
FEATURED · 精选文章 
1. 项目概述从一道蓝桥杯真题看算法思维的本质看到“ALGO-451 铺地板”这个标题很多正在备战蓝桥杯或者刚接触算法竞赛的同学可能会心头一紧。铺地板听起来像是一道动态规划DP或者搜索题而且蓝桥杯的ALGO系列向来以考察基础算法思想和代码实现能力著称。这道题目的核心远不止是计算如何用砖块填满一个房间那么简单。它本质上是一个经典的“棋盘覆盖”或“区域填充”问题的变种是理解递归、分治、状态压缩乃至更深层次组合数学的绝佳入口。我当年第一次碰到这类题目时也是绕了不少弯路总觉得情况复杂状态难以表示。后来经过大量练习和总结才发现这类问题有清晰的解决路径和思维模式。今天我就结合这道“铺地板”真题把这类问题的解题心法、代码实现中的关键细节以及如何从一道题扩展到一类题的思考过程完整地梳理一遍。无论你是正在刷题备赛的选手还是对算法感兴趣想提升逻辑思维能力的开发者相信这篇从实战中沉淀下来的经验都能让你对“如何解决一个复杂问题”有更透彻的认识。2. 问题核心与数学模型抽象2.1 题目场景还原与约束分析虽然我们手头没有ALGO-451的原始题面但根据“铺地板”这个经典模型和蓝桥杯的命题风格我们可以准确地还原出问题的典型描述。通常这类问题会给定一个M x N大小的网格区域代表房间地板以及一种或几种固定尺寸的砖块比如1x2的长方形砖也就是多米诺骨牌。问题要求计算使用给定的砖块恰好铺满整个网格区域有多少种不同的铺设方案砖块可以旋转但不能重叠也不能超出网格边界。这里面的核心约束和难点立刻浮现出来完全覆盖必须铺满所有格子不能有空缺。砖块形状固定通常是1x2或2x1两者等价可通过旋转实现有时也会引入2x2的L形砖等增加复杂度。方案计数不是找出一种方案而是计算所有可能的方案总数。这个数字往往非常巨大对算法效率是极大考验。为什么这个问题重要因为它直接对应着状态压缩动态规划的经典应用。网格的每一行其被砖块覆盖的状态可以用一个二进制数来表示例如0表示该格子未被当前行新铺的砖覆盖1表示已被覆盖。我们需要逐行决策并且当前行的铺设方式会受到上一行状态的影响。这就像是在完成一个巨大的、有严格规则的拼图每一步的选择都会影响后续所有步骤。2.2 状态压缩动态规划状压DP思路拆解面对M和N可能达到10甚至20的量级暴力搜索所有铺法DFS是完全不可行的。状态压缩DP是几乎唯一的可行正道。其核心思想是将每一行的铺设状态压缩成一个整数然后研究相邻行状态之间的合法转移关系。我们来一步步拆解这个思维过程第一步状态定义我们定义dp[i][state]表示当前处理到第i行并且第i行的覆盖状态为state时铺满前i行总共的方案数。这里state是一个N位的二进制数它的第j位从低位到高位表示第i行第j列格子的覆盖情况。但需要注意的是这个“覆盖情况”指的是来自第i行新放置的砖块对当前行造成的覆盖。一个更精准的理解是state中为1的格子表示这个格子是一个“砖块的起点”比如一个横砖的左端或一个竖砖的上端。第二步状态转移这是最关键也是最难理解的部分。转移发生在从第i-1行到第i行。当我们决定第i行的铺设状态cur时必须满足以下条件cur与上一行的状态prev不能冲突。具体来说prev中为1的格子表示第i-1行有一个竖砖的下端延伸到了第i行。因此在第i行这些对应的格子必须被填充即cur的对应位必须为1并且这个“1”是由上一行的竖砖带来的而不是本行新砖的起点。在满足了上一行竖砖的约束后cur中剩下的为0的格子本行必须用横砖去覆盖。因为竖砖已经由上一步决定了本行新放的砖只能是横砖起点在cur中标记为1去覆盖两个连续的0。所以我们需要检查cur中剩余的0是否都能两两配对形成合法的横砖放置。这个过程可以转化为一个预处理对于所有可能的cur状态找出所有能与它合法搭配的prev状态。然后转移方程为dp[i][cur] dp[i-1][prev]。第三步初始化与最终答案初始化dp[0][0] 1表示第0行一个虚拟的行已经完全铺好状态为0有一种方案。 最终答案是dp[M][0]表示处理完所有M行后最后一行没有任何砖块需要延伸到下一行状态为0即整个网格被完美铺满。注意这里有一个非常重要的技巧就是按“行”进行DP时我们实际编码中常常会使用“轮廓线DP”或者“插头DP”的思想一次推进一格而不是一整行。但对于理解基础模型按行划分状态已经足够。在实际处理时我们常常会使用DFS来生成一行内所有合法的横砖摆放方式这本身也是一个递归过程。3. 关键实现细节与深度解析3.1 预处理生成一行内的所有合法状态在状态转移中我们需要知道对于某个prev状态哪些cur状态是合法的。更高效的做法是预处理出所有一行之内的合法摆放状态。所谓一行内的合法状态是指忽略上一行的影响仅在本行内放置砖块此时只允许放横砖所有格子都被覆盖的状态。如何生成这是一个经典的深度优先搜索DFS问题。我们从第0列开始逐列扫描如果当前列已经被覆盖可能是上一行竖砖延伸下来的在本阶段预处理中我们假设所有格子初始未覆盖则跳到下一列。如果当前列未被覆盖我们有两种选择因为竖砖是跨行的在一行内预处理时不考虑放一块横砖覆盖当前列和下一列。这要求下一列存在且未被覆盖。不放砖这是不可能的因为我们要覆盖所有格子。所以实际上只有第一种选择是有效的。通过DFS我们可以枚举出所有用横砖铺满一行N列的方法每一种方法对应一个二进制状态state。在这个状态中被横砖覆盖的左端格子标记为1。这些状态集合就是我们后续DP中进行行内横砖填充的“零件库”。// 示例DFS函数用于生成一行内所有合法的横砖铺设状态 vectorint states; // 存储所有合法状态 int N; // 列数 void dfs(int col, int state) { if (col N) { // 已经处理完所有列找到一个合法状态 states.push_back(state); return; } // 如果当前列已被覆盖在state中已标记则直接处理下一列 if (state (1 col)) { dfs(col 1, state); return; } // 否则尝试在当前列放置一块横砖覆盖col和col1 if (col 1 N !(state (1 (col 1)))) { int newState state | (1 col) | (1 (col 1)); dfs(col 2, newState); // 跳过后一列因为已经被覆盖 } // 注意不能不放砖因为我们要铺满所有格子。所以没有“不放砖”的分支。 } // 初始化调用dfs(0, 0);3.2 状态转移的代码实现与优化有了行内合法状态集合states我们就可以构建状态转移矩阵。对于任意两个状态prev和cur它们能转移的条件是(prev | cur) (1 N) - 1且(prev cur)中的每个1在cur中都是由prev的竖砖延伸下来的。实际上更常用的判断方法是首先prev cur的结果记为intersection中的1代表了那些被上一行竖砖占据本行位置的格子。这些格子必须在cur中是1。然后从cur中剔除掉这些必须的1即cur ^ intersection剩下的1就代表本行新放置的横砖的起点。我们需要检查这些剩下的1所构成的状态是否属于我们预处理的states集合即能否用横砖完美覆盖。在实际编码中为了加速我们常常会进行二次预处理建立一个二维数组transition[prev][cur]或一个向量表nextStates[prev]直接存储从状态prev可以转移到哪些状态cur。这样在DP循环中就可以直接遍历nextStates[prev]将dp[i-1][prev]加到dp[i][cur]上。// 示例DP核心循环按行推进 vectorvectorlong long dp(M 1, vectorlong long(1 N, 0)); dp[0][0] 1; // 初始化 for (int i 1; i M; i) { for (int prev 0; prev (1 N); prev) { if (dp[i-1][prev] 0) continue; // 剪枝无效状态跳过 // 遍历所有可以从prev转移到的cur状态 for (int cur : nextStates[prev]) { dp[i][cur] dp[i-1][prev]; } } } long long ans dp[M][0]; // 最终答案内存与时间优化当N较大时比如15状态总数是2^1532768两层循环加上遍历转移状态复杂度是O(M * 2^N * K)其中K是平均转移数。这可能会超时或超内存。常见的优化是滚动数组由于dp[i]只依赖于dp[i-1]我们可以只用两个一维数组dp_curr和dp_prev交替使用将空间复杂度从O(M * 2^N)降到O(2^N)。剪枝无效状态很多状态是无法从任何状态转移而来的或者无法转移到任何状态。在预处理nextStates时就可以发现DP过程中只处理有效的状态。4. 从解题到通法一类问题的思考框架4.1 铺地板问题的常见变体与应对策略掌握了基础模型我们就能应对各种变体这也是蓝桥杯等竞赛常见的考察方式。变体1砖块种类增加例如除了1x2的砖还有2x2的方块砖或者L形的三格砖。这时状态定义和转移会变得异常复杂。应对策略状态可能需要额外信息。对于2x2砖它会影响两行因此我们的状态可能需要同时表示两行的覆盖情况。这时“轮廓线DP”的优势就体现出来了它把状态定义为当前处理格子左侧和上方若干个格子的覆盖情况更适合处理复杂形状。核心思路不变依然是定义状态、寻找合法转移但状态维度和转移判断逻辑会几何级数增长。变体2网格中存在障碍物某些格子不能铺砖。这是非常经典的变体。应对策略在状态表示中融入障碍信息。我们可以将每一行的障碍物分布也压缩成一个二进制掩码block_mask。在生成合法状态和进行状态转移时必须满足任何砖块都不能覆盖block_mask中为1的格子。具体来说在DFS生成行内状态时如果当前位置是障碍则不能作为砖块起点在判断行间转移时cur状态不能在任何障碍位上是1除非这个1是由上一行竖砖延伸下来覆盖了障碍但通常障碍格不允许被覆盖所以这个“除非”也不成立。这相当于对状态空间加了一个硬性约束。变体3求具体方案而非方案数要求输出任意一种或所有铺设方案。应对策略DP过程不仅可以记录方案数还可以记录“前驱状态”。在完成DP后从最终状态dp[M][0]开始根据记录的前驱状态反向回溯就能重建出一种铺设方案。如果要输出所有方案则需要用DFS在状态转移图上进行搜索但方案数可能巨大通常只适用于小规模数据。4.2 调试技巧与常见“坑点”实录在实现这类状压DP时极易出错。下面是我在无数次WAWrong Answer中总结出的排查清单初始化错误dp[0][0]必须设为1。有时会错误地将dp[0][所有行内合法状态]设为1这是不对的因为第0行是虚拟行必须是完全铺好的状态0才能开始第一行的铺设。状态含义混淆最致命的就是搞不清状态state中“1”和“0”的确切含义。务必统一在我的定义中state的“1”表示当前行新放置砖块的起始格。竖砖的延伸部分在下一行看来是一个“必须被填充的约束”而不是下一行新砖的起点。转移条件判断错误特别是prev cur和prev | cur的运用。务必写一个小型的测试程序手动枚举N3或4的所有prev和cur打印出你认为合法的转移对然后与暴力搜索的结果对比验证。这是调试预处理逻辑最有效的方法。整数溢出方案数增长极快MN10时答案就可能超过int范围。务必使用long longC或高精度整数。行列数处理如果M或N为1需要特判。例如1xN的网格只用横砖只有N为偶数时才有1种方案全横铺否则为0。Mx1的网格只用竖砖只有M为偶数时才有1种方案。DFS生成状态不完整或重复确保你的DFS函数能覆盖所有可能的横砖摆放方式。对于N4横铺状态有(1100, 0011, 1111)吗1111是合法的吗不1111表示四个格子都是起点这不可能因为一块横砖覆盖两个格子需要两个起点。所以1111不是合法的行内状态。检查你的状态生成逻辑是否正确排除了这类无效状态。一个非常实用的调试技巧不要一上来就写完整的DP。先写一个暴力DFS函数用于在小规模如M3, N4网格上枚举所有铺法并计数。这个暴力程序的结果将是你优化算法状压DP的绝对正确参照。确保你的DP程序在M和N很小时的结果与暴力枚举完全一致然后再去挑战更大的数据。这能帮你快速定位是状态定义、转移逻辑还是边界条件出了问题。5. 性能优化与高阶探索5.1 矩阵快速幂优化当行数M极大时上述DP的时间复杂度是O(M * 2^N * K)。如果N不大比如N10但M非常大比如M10^9这种线性DP就会超时。这时我们需要观察到状态转移是一个线性递推关系并且转移方式对于每一行都是相同的无后效性。我们可以把状态转移关系抽象成一个矩阵T其中T[prev][cur] 1表示可以从状态prev转移到状态cur否则为0。那么从第0行到第M行的转移就相当于初始向量V0只有V0[0]1其余为0乘以矩阵T的M次方V_M V0 * (T^M)。最终答案就是V_M[0]。矩阵的M次方可以通过矩阵快速幂在O((2^N)^3 * log M)时间内计算出来。虽然(2^N)^3在N10时是1024^3仍然很大但通过稀疏矩阵优化和log M的因子可以处理M极大的情况。这是解决此类“线性递推巨大步数”问题的标准武器。5.2 轮廓线DP更通用的思维模型我们之前讨论的是“按行DP”状态表示的是一整行的覆盖情况。而轮廓线DP是更细致、更强大的模型。它的状态定义为当前处理到网格(i, j)位置时一个“轮廓线”的覆盖情况。这条轮廓线通常包含当前格子左侧和上方若干个相邻格子的覆盖状态。轮廓线DP的优势在于天然适合复杂形状砖块因为状态是局部化的判断一个L形砖能否放置只需要看周围几个格子的状态比整行状态更容易处理。节省状态空间轮廓线状态的长度通常是N1当前行已处理的N个格子下一行的一个格子而不是整行的N。状态总数仍然是2^(N1)但在处理复杂形状时逻辑更清晰。便于处理障碍物障碍物信息可以很容易地融入到逐格推进的过程中。轮廓线DP的代码实现通常更复杂因为它是在网格上逐格进行转移状态转移方程需要根据当前格是空白、已覆盖、是障碍等不同情况分别讨论。但它确实是解决更复杂铺砖问题的终极工具。学习轮廓线DP建议从经典的“骨牌铺满”问题开始画出状态转移图一步步理解轮廓线上每个比特位的含义。6. 总结与心法提炼回顾这道“铺地板”问题它的价值远超一道算法题。它训练了我们几种核心能力第一复杂问题的建模能力。如何将一个具体的、感性的“铺砖”问题抽象成二进制状态和状态转移的数学模型这是计算机解决任何现实问题的第一步。第二对动态规划本质的理解。DP不是背模板而是定义状态描述局面、找到状态之间的递推关系决策如何改变局面、确定边界最初局面和目标最终局面。铺地板问题是展示这一过程的完美范例。第三对位运算的熟练掌握。状态压缩离不开位运算。快速判断二进制位的覆盖、冲突、合法性是高效实现这类算法的基本功。第四调试和验证思维。先写暴力程序定标再逐步优化这种“双保险”的解题策略在工程开发和算法竞赛中同样重要。最后我的个人体会是学习算法切忌只记代码。像“铺地板”这类题目一定要亲手画一画N3, M3的网格枚举几种铺法再去理解状态010、101代表什么它们之间为什么能转移、为什么不能转移。当你能在纸上把状态转移图画出来的时候代码实现就只是水到渠成的翻译工作。蓝桥杯的很多题目包括ALGO系列考察的正是这种扎实的、从原理到实现的贯通能力。把这道题吃透状压DP的大门才算真正向你敞开。
蓝桥杯铺地板真题解析：状态压缩动态规划与棋盘覆盖算法实战
1. 项目概述从一道蓝桥杯真题看算法思维的本质看到“ALGO-451 铺地板”这个标题很多正在备战蓝桥杯或者刚接触算法竞赛的同学可能会心头一紧。铺地板听起来像是一道动态规划DP或者搜索题而且蓝桥杯的ALGO系列向来以考察基础算法思想和代码实现能力著称。这道题目的核心远不止是计算如何用砖块填满一个房间那么简单。它本质上是一个经典的“棋盘覆盖”或“区域填充”问题的变种是理解递归、分治、状态压缩乃至更深层次组合数学的绝佳入口。我当年第一次碰到这类题目时也是绕了不少弯路总觉得情况复杂状态难以表示。后来经过大量练习和总结才发现这类问题有清晰的解决路径和思维模式。今天我就结合这道“铺地板”真题把这类问题的解题心法、代码实现中的关键细节以及如何从一道题扩展到一类题的思考过程完整地梳理一遍。无论你是正在刷题备赛的选手还是对算法感兴趣想提升逻辑思维能力的开发者相信这篇从实战中沉淀下来的经验都能让你对“如何解决一个复杂问题”有更透彻的认识。2. 问题核心与数学模型抽象2.1 题目场景还原与约束分析虽然我们手头没有ALGO-451的原始题面但根据“铺地板”这个经典模型和蓝桥杯的命题风格我们可以准确地还原出问题的典型描述。通常这类问题会给定一个M x N大小的网格区域代表房间地板以及一种或几种固定尺寸的砖块比如1x2的长方形砖也就是多米诺骨牌。问题要求计算使用给定的砖块恰好铺满整个网格区域有多少种不同的铺设方案砖块可以旋转但不能重叠也不能超出网格边界。这里面的核心约束和难点立刻浮现出来完全覆盖必须铺满所有格子不能有空缺。砖块形状固定通常是1x2或2x1两者等价可通过旋转实现有时也会引入2x2的L形砖等增加复杂度。方案计数不是找出一种方案而是计算所有可能的方案总数。这个数字往往非常巨大对算法效率是极大考验。为什么这个问题重要因为它直接对应着状态压缩动态规划的经典应用。网格的每一行其被砖块覆盖的状态可以用一个二进制数来表示例如0表示该格子未被当前行新铺的砖覆盖1表示已被覆盖。我们需要逐行决策并且当前行的铺设方式会受到上一行状态的影响。这就像是在完成一个巨大的、有严格规则的拼图每一步的选择都会影响后续所有步骤。2.2 状态压缩动态规划状压DP思路拆解面对M和N可能达到10甚至20的量级暴力搜索所有铺法DFS是完全不可行的。状态压缩DP是几乎唯一的可行正道。其核心思想是将每一行的铺设状态压缩成一个整数然后研究相邻行状态之间的合法转移关系。我们来一步步拆解这个思维过程第一步状态定义我们定义dp[i][state]表示当前处理到第i行并且第i行的覆盖状态为state时铺满前i行总共的方案数。这里state是一个N位的二进制数它的第j位从低位到高位表示第i行第j列格子的覆盖情况。但需要注意的是这个“覆盖情况”指的是来自第i行新放置的砖块对当前行造成的覆盖。一个更精准的理解是state中为1的格子表示这个格子是一个“砖块的起点”比如一个横砖的左端或一个竖砖的上端。第二步状态转移这是最关键也是最难理解的部分。转移发生在从第i-1行到第i行。当我们决定第i行的铺设状态cur时必须满足以下条件cur与上一行的状态prev不能冲突。具体来说prev中为1的格子表示第i-1行有一个竖砖的下端延伸到了第i行。因此在第i行这些对应的格子必须被填充即cur的对应位必须为1并且这个“1”是由上一行的竖砖带来的而不是本行新砖的起点。在满足了上一行竖砖的约束后cur中剩下的为0的格子本行必须用横砖去覆盖。因为竖砖已经由上一步决定了本行新放的砖只能是横砖起点在cur中标记为1去覆盖两个连续的0。所以我们需要检查cur中剩余的0是否都能两两配对形成合法的横砖放置。这个过程可以转化为一个预处理对于所有可能的cur状态找出所有能与它合法搭配的prev状态。然后转移方程为dp[i][cur] dp[i-1][prev]。第三步初始化与最终答案初始化dp[0][0] 1表示第0行一个虚拟的行已经完全铺好状态为0有一种方案。 最终答案是dp[M][0]表示处理完所有M行后最后一行没有任何砖块需要延伸到下一行状态为0即整个网格被完美铺满。注意这里有一个非常重要的技巧就是按“行”进行DP时我们实际编码中常常会使用“轮廓线DP”或者“插头DP”的思想一次推进一格而不是一整行。但对于理解基础模型按行划分状态已经足够。在实际处理时我们常常会使用DFS来生成一行内所有合法的横砖摆放方式这本身也是一个递归过程。3. 关键实现细节与深度解析3.1 预处理生成一行内的所有合法状态在状态转移中我们需要知道对于某个prev状态哪些cur状态是合法的。更高效的做法是预处理出所有一行之内的合法摆放状态。所谓一行内的合法状态是指忽略上一行的影响仅在本行内放置砖块此时只允许放横砖所有格子都被覆盖的状态。如何生成这是一个经典的深度优先搜索DFS问题。我们从第0列开始逐列扫描如果当前列已经被覆盖可能是上一行竖砖延伸下来的在本阶段预处理中我们假设所有格子初始未覆盖则跳到下一列。如果当前列未被覆盖我们有两种选择因为竖砖是跨行的在一行内预处理时不考虑放一块横砖覆盖当前列和下一列。这要求下一列存在且未被覆盖。不放砖这是不可能的因为我们要覆盖所有格子。所以实际上只有第一种选择是有效的。通过DFS我们可以枚举出所有用横砖铺满一行N列的方法每一种方法对应一个二进制状态state。在这个状态中被横砖覆盖的左端格子标记为1。这些状态集合就是我们后续DP中进行行内横砖填充的“零件库”。// 示例DFS函数用于生成一行内所有合法的横砖铺设状态 vectorint states; // 存储所有合法状态 int N; // 列数 void dfs(int col, int state) { if (col N) { // 已经处理完所有列找到一个合法状态 states.push_back(state); return; } // 如果当前列已被覆盖在state中已标记则直接处理下一列 if (state (1 col)) { dfs(col 1, state); return; } // 否则尝试在当前列放置一块横砖覆盖col和col1 if (col 1 N !(state (1 (col 1)))) { int newState state | (1 col) | (1 (col 1)); dfs(col 2, newState); // 跳过后一列因为已经被覆盖 } // 注意不能不放砖因为我们要铺满所有格子。所以没有“不放砖”的分支。 } // 初始化调用dfs(0, 0);3.2 状态转移的代码实现与优化有了行内合法状态集合states我们就可以构建状态转移矩阵。对于任意两个状态prev和cur它们能转移的条件是(prev | cur) (1 N) - 1且(prev cur)中的每个1在cur中都是由prev的竖砖延伸下来的。实际上更常用的判断方法是首先prev cur的结果记为intersection中的1代表了那些被上一行竖砖占据本行位置的格子。这些格子必须在cur中是1。然后从cur中剔除掉这些必须的1即cur ^ intersection剩下的1就代表本行新放置的横砖的起点。我们需要检查这些剩下的1所构成的状态是否属于我们预处理的states集合即能否用横砖完美覆盖。在实际编码中为了加速我们常常会进行二次预处理建立一个二维数组transition[prev][cur]或一个向量表nextStates[prev]直接存储从状态prev可以转移到哪些状态cur。这样在DP循环中就可以直接遍历nextStates[prev]将dp[i-1][prev]加到dp[i][cur]上。// 示例DP核心循环按行推进 vectorvectorlong long dp(M 1, vectorlong long(1 N, 0)); dp[0][0] 1; // 初始化 for (int i 1; i M; i) { for (int prev 0; prev (1 N); prev) { if (dp[i-1][prev] 0) continue; // 剪枝无效状态跳过 // 遍历所有可以从prev转移到的cur状态 for (int cur : nextStates[prev]) { dp[i][cur] dp[i-1][prev]; } } } long long ans dp[M][0]; // 最终答案内存与时间优化当N较大时比如15状态总数是2^1532768两层循环加上遍历转移状态复杂度是O(M * 2^N * K)其中K是平均转移数。这可能会超时或超内存。常见的优化是滚动数组由于dp[i]只依赖于dp[i-1]我们可以只用两个一维数组dp_curr和dp_prev交替使用将空间复杂度从O(M * 2^N)降到O(2^N)。剪枝无效状态很多状态是无法从任何状态转移而来的或者无法转移到任何状态。在预处理nextStates时就可以发现DP过程中只处理有效的状态。4. 从解题到通法一类问题的思考框架4.1 铺地板问题的常见变体与应对策略掌握了基础模型我们就能应对各种变体这也是蓝桥杯等竞赛常见的考察方式。变体1砖块种类增加例如除了1x2的砖还有2x2的方块砖或者L形的三格砖。这时状态定义和转移会变得异常复杂。应对策略状态可能需要额外信息。对于2x2砖它会影响两行因此我们的状态可能需要同时表示两行的覆盖情况。这时“轮廓线DP”的优势就体现出来了它把状态定义为当前处理格子左侧和上方若干个格子的覆盖情况更适合处理复杂形状。核心思路不变依然是定义状态、寻找合法转移但状态维度和转移判断逻辑会几何级数增长。变体2网格中存在障碍物某些格子不能铺砖。这是非常经典的变体。应对策略在状态表示中融入障碍信息。我们可以将每一行的障碍物分布也压缩成一个二进制掩码block_mask。在生成合法状态和进行状态转移时必须满足任何砖块都不能覆盖block_mask中为1的格子。具体来说在DFS生成行内状态时如果当前位置是障碍则不能作为砖块起点在判断行间转移时cur状态不能在任何障碍位上是1除非这个1是由上一行竖砖延伸下来覆盖了障碍但通常障碍格不允许被覆盖所以这个“除非”也不成立。这相当于对状态空间加了一个硬性约束。变体3求具体方案而非方案数要求输出任意一种或所有铺设方案。应对策略DP过程不仅可以记录方案数还可以记录“前驱状态”。在完成DP后从最终状态dp[M][0]开始根据记录的前驱状态反向回溯就能重建出一种铺设方案。如果要输出所有方案则需要用DFS在状态转移图上进行搜索但方案数可能巨大通常只适用于小规模数据。4.2 调试技巧与常见“坑点”实录在实现这类状压DP时极易出错。下面是我在无数次WAWrong Answer中总结出的排查清单初始化错误dp[0][0]必须设为1。有时会错误地将dp[0][所有行内合法状态]设为1这是不对的因为第0行是虚拟行必须是完全铺好的状态0才能开始第一行的铺设。状态含义混淆最致命的就是搞不清状态state中“1”和“0”的确切含义。务必统一在我的定义中state的“1”表示当前行新放置砖块的起始格。竖砖的延伸部分在下一行看来是一个“必须被填充的约束”而不是下一行新砖的起点。转移条件判断错误特别是prev cur和prev | cur的运用。务必写一个小型的测试程序手动枚举N3或4的所有prev和cur打印出你认为合法的转移对然后与暴力搜索的结果对比验证。这是调试预处理逻辑最有效的方法。整数溢出方案数增长极快MN10时答案就可能超过int范围。务必使用long longC或高精度整数。行列数处理如果M或N为1需要特判。例如1xN的网格只用横砖只有N为偶数时才有1种方案全横铺否则为0。Mx1的网格只用竖砖只有M为偶数时才有1种方案。DFS生成状态不完整或重复确保你的DFS函数能覆盖所有可能的横砖摆放方式。对于N4横铺状态有(1100, 0011, 1111)吗1111是合法的吗不1111表示四个格子都是起点这不可能因为一块横砖覆盖两个格子需要两个起点。所以1111不是合法的行内状态。检查你的状态生成逻辑是否正确排除了这类无效状态。一个非常实用的调试技巧不要一上来就写完整的DP。先写一个暴力DFS函数用于在小规模如M3, N4网格上枚举所有铺法并计数。这个暴力程序的结果将是你优化算法状压DP的绝对正确参照。确保你的DP程序在M和N很小时的结果与暴力枚举完全一致然后再去挑战更大的数据。这能帮你快速定位是状态定义、转移逻辑还是边界条件出了问题。5. 性能优化与高阶探索5.1 矩阵快速幂优化当行数M极大时上述DP的时间复杂度是O(M * 2^N * K)。如果N不大比如N10但M非常大比如M10^9这种线性DP就会超时。这时我们需要观察到状态转移是一个线性递推关系并且转移方式对于每一行都是相同的无后效性。我们可以把状态转移关系抽象成一个矩阵T其中T[prev][cur] 1表示可以从状态prev转移到状态cur否则为0。那么从第0行到第M行的转移就相当于初始向量V0只有V0[0]1其余为0乘以矩阵T的M次方V_M V0 * (T^M)。最终答案就是V_M[0]。矩阵的M次方可以通过矩阵快速幂在O((2^N)^3 * log M)时间内计算出来。虽然(2^N)^3在N10时是1024^3仍然很大但通过稀疏矩阵优化和log M的因子可以处理M极大的情况。这是解决此类“线性递推巨大步数”问题的标准武器。5.2 轮廓线DP更通用的思维模型我们之前讨论的是“按行DP”状态表示的是一整行的覆盖情况。而轮廓线DP是更细致、更强大的模型。它的状态定义为当前处理到网格(i, j)位置时一个“轮廓线”的覆盖情况。这条轮廓线通常包含当前格子左侧和上方若干个相邻格子的覆盖状态。轮廓线DP的优势在于天然适合复杂形状砖块因为状态是局部化的判断一个L形砖能否放置只需要看周围几个格子的状态比整行状态更容易处理。节省状态空间轮廓线状态的长度通常是N1当前行已处理的N个格子下一行的一个格子而不是整行的N。状态总数仍然是2^(N1)但在处理复杂形状时逻辑更清晰。便于处理障碍物障碍物信息可以很容易地融入到逐格推进的过程中。轮廓线DP的代码实现通常更复杂因为它是在网格上逐格进行转移状态转移方程需要根据当前格是空白、已覆盖、是障碍等不同情况分别讨论。但它确实是解决更复杂铺砖问题的终极工具。学习轮廓线DP建议从经典的“骨牌铺满”问题开始画出状态转移图一步步理解轮廓线上每个比特位的含义。6. 总结与心法提炼回顾这道“铺地板”问题它的价值远超一道算法题。它训练了我们几种核心能力第一复杂问题的建模能力。如何将一个具体的、感性的“铺砖”问题抽象成二进制状态和状态转移的数学模型这是计算机解决任何现实问题的第一步。第二对动态规划本质的理解。DP不是背模板而是定义状态描述局面、找到状态之间的递推关系决策如何改变局面、确定边界最初局面和目标最终局面。铺地板问题是展示这一过程的完美范例。第三对位运算的熟练掌握。状态压缩离不开位运算。快速判断二进制位的覆盖、冲突、合法性是高效实现这类算法的基本功。第四调试和验证思维。先写暴力程序定标再逐步优化这种“双保险”的解题策略在工程开发和算法竞赛中同样重要。最后我的个人体会是学习算法切忌只记代码。像“铺地板”这类题目一定要亲手画一画N3, M3的网格枚举几种铺法再去理解状态010、101代表什么它们之间为什么能转移、为什么不能转移。当你能在纸上把状态转移图画出来的时候代码实现就只是水到渠成的翻译工作。蓝桥杯的很多题目包括ALGO系列考察的正是这种扎实的、从原理到实现的贯通能力。把这道题吃透状压DP的大门才算真正向你敞开。 
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
