蓝桥杯国赛题解：从搭积木到状态压缩动态规划的思维跃迁

1. 项目概述从“搭积木”到“状态压缩DP”的思维跃迁“蓝桥杯18年国赛 搭积木”这个标题乍一看可能会让一些刚接触算法竞赛的同学感到困惑。搭积木这不是小朋友玩的游戏吗怎么会出现在以算法和编程为核心的蓝桥杯国赛舞台上这正是这道题目的精妙之处也是蓝桥杯一贯的出题风格用一个生活化、具象化的场景包裹一个经典的、需要深度算法思维才能解决的计算机科学问题。它不是真的让你去模拟搭积木的物理过程而是将“搭积木”这个行为抽象成一个数学模型考察你对动态规划Dynamic Programming, DP特别是状态压缩动态规划这一高阶技巧的理解和应用能力。这道题在当年的国赛中属于中等偏上的难度是区分选手水平的关键题目之一。它要求选手不仅要有扎实的编程基础更要具备将实际问题转化为数学模型并设计高效算法求解的抽象思维能力。对于正在备赛蓝桥杯尤其是目标冲击省一、国奖的选手来说吃透这道题及其背后的思想价值远超题目本身。它能帮你打通“状态压缩DP”这一重要关隘让你在面对诸如棋盘覆盖、任务安排、集合划分等一类问题时拥有一个强大而通用的解题武器库。接下来我将以一个过来人的视角为你彻底拆解这道题从题意理解、思路分析、状态设计、代码实现到优化技巧手把手带你攻克这个经典难题。2. 题意解析与问题抽象积木背后的数学约束首先我们必须抛开“积木”的具象外壳直击其数学本质。根据题目描述这里基于常见的回忆和题解进行还原具体细节可能因回忆有细微出入但核心不变我们可以将题意抽象如下我们有一个高度为10这是一个关键数字通常题目会给定一个不大的高度上限10便于状态压缩的“空间”或“地基”。我们有若干块积木每块积木有固定的高度和颜色。题目会给定一个最终的“目标状态”即一堵由这些积木堆叠而成的“墙”我们能看到其每一列的最终颜色或者说每一列从下到上积木颜色的序列。我们的任务是计算出使用给定的积木每块积木必须使用恰好一次有多少种不同的搭建顺序可以最终得到这个目标状态。这里隐藏了几个至关重要的约束和条件需要仔细品味搭建规则这通常是核心。积木必须从底部开始搭建并且放置时必须保证稳定性。最常见的抽象规则是当你放置一块新积木时它必须放置在已有积木的顶部并且其底部必须被完全支撑。在二维的简化模型中这常常被转化为对于每一列当前已放置的积木高度必须是连续的不能出现“悬空”。这意味着在搭建过程中的任意时刻从地基向上的积木堆叠是连续的侧面看是一个“阶梯”状或“完整”的轮廓。状态观测我们只关心最终每一列的颜色排列而不关心具体是哪一块积木因为颜色可能重复。但搭建顺序不同即使最终颜色排列相同也算作不同的方案。这提示我们我们的动态规划状态需要记录当前搭建的进度轮廓而进度轮廓直接决定了下一步哪些积木可以放置。数据规模积木的数量比如n 20和高度上限H10是算法设计的决定性因素。n20暗示我们可能需要枚举所有积木的使用情况2^20 1,048,576这是百万级别是可接受的状态压缩的典型范围。高度H10则意味着我们可以用一个整数如int的二进制位来精确表示每一列当前的高度或更具体地说当前轮廓的形状。经过这样的抽象“搭积木”问题就变成了给定一个最终的目标颜色矩阵列数W * 高度H以及一堆积木每个有高度h和颜色c求所有能使搭建过程中每一时刻轮廓连续且最终颜色分布符合目标的搭建顺序方案数。注意不同的题目回忆版本可能在“颜色”的具体含义是每块积木的颜色还是最终表面的颜色、目标状态的描述方式上略有不同。但核心考点——基于轮廓的状态压缩DP——是高度一致的。我们的解法将围绕这个核心展开。3. 核心算法思想轮廓线动态规划插头DP/状态压缩DP面对这个问题暴力枚举所有排列顺序显然是不可行的n! 巨大无比。我们需要发现问题的重叠子结构并应用动态规划。一个最直观的DP想法是dp[i][mask]表示已经使用了mask这个集合表示的积木状态压缩当前搭建的整体高度轮廓为i的方案数。但“整体高度轮廓”很难用一个简单的i表示它需要描述每一列的具体高度因为放置规则和最终目标都依赖于每一列的细节。这就引出了本题的核心算法——基于轮廓线的状态压缩动态规划有时也被称为“插头DP”在棋盘覆盖类问题中的一种变体。其核心思想是定义轮廓线我们想象一个扫描线从地基的最左侧一列开始一列一列地向右扫描搭建进度。在任意时刻“轮廓线”描述了当前已搭建区域与未搭建区域或地基的边界。由于搭建必须从底部连续向上这条轮廓线可以被描述为每一列的当前高度。因为高度上限H10我们可以用0到10的数字表示每一列的高度整个轮廓就是一个长度为W总列数的整数数组。状态压缩为了将轮廓线作为DP的状态我们需要将其编码成一个可以放入数组索引的整数。由于每列高度不超过10我们可以用4位二进制bit来表示一列的高度因为2^41610。那么对于W列我们总共需要W * 4位。如果W10就需要40位这超过了普通32位整数的范围但可以使用64位整数long long来存储。状态值state就是这个编码后的轮廓线。状态转移状态dp[state]表示达到轮廓线state的方案数。转移时我们考虑在当前轮廓线上下一步可以放置哪些积木放置一块高度为h、颜色为c的积木需要满足该积木尚未被使用需要在状态中额外记录积木的使用情况或者更常见的我们将积木的放置顺序融入DP过程即DP状态只记录轮廓而通过“当前已放置积木数量”或“已使用积木集合”来隐含顺序信息。但更优的方法是预处理所有积木并规定放置顺序然后DP计数。这里有一个关键技巧由于积木不可区分同颜色同高度我们通常先对积木按某种规则排序然后规定放置必须按照排序后的顺序进行这样避免了重复计数同时将“使用了哪些积木”的信息转化为“放置到了第几块积木”。放置的位置必须满足“连续支撑”条件。通常这意味着一块高度为h的积木只能放置在一个当前轮廓线是平坦的、且长度至少为h的连续横坐标区间上。放置后该区间的轮廓线高度全部增加h。与最终目标匹配在DP过程中或最终我们需要检查轮廓线状态是否与最终目标颜色矩阵匹配。匹配意味着对于每一列从底部到高度state中该列高度的位置其颜色序列必须与目标矩阵中该列从下往上的颜色序列一致。这可以在状态转移时作为约束条件也可以在DP结束后过滤有效状态。然而上述描述的方法状态空间可能非常大(H1)^W即使压缩后也未必可行。因此经典的解法往往采用另一种更巧妙的状态定义和转移方式这也是本题最精彩的部分。4. 经典解法深度剖析按列转移与高度编码更高效的解法是按列进行DP。考虑到最终目标是以列为单位的颜色序列按列处理更为自然。我们定义dp[i][s]表示已经处理完前i列即前i列的最终颜色已经和目标匹配并且当前第i列的处理高度或者说处理完前i列后整个搭建进度在最右侧形成的轮廓线在i1列处的高度为s的方案数。这里的s是一个高度状态但它不是单一数字因为第i列右侧可能是一个复杂的轮廓。但通过巧妙的设置我们可以简化。实际上一个广为流传的经典状态定义是dp[i][mask]表示已经正确搭建好了前i列并且第i列之后的若干列即未处理区域的“相对高度差”或“轮廓形状”为mask的方案数。这个mask编码了从第i1列开始每一列当前已搭建的高度相对于一个基准线比如第i列的高度的差值。为什么这样定义因为放置积木的“连续支撑”规则决定了你在第i列放置一块积木时它可能会影响到第i1, i2…列如果积木横跨多列。因此要决定下一块积木能否放置不仅要知道当前列的高度还要知道后面几列的相对高度以确保放置后不会违反连续规则。一个更具体、更常见的实现框架如下假设积木都是11的单位方块颜色附着在方块上目标是一个WH的颜色网格状态设计dp[i][j][mask]。i表示当前正在放置的行从下往上0代表地基j表示当前列从左到右mask是一个长度为W的二进制状态表示在当前行i哪些列已经被积木覆盖1表示该列在行i已经有积木0表示空。这个状态描述的是“当前铺设轮廓”的俯视图切片。转移过程我们从左下角开始一行一行、一列一列地放置单位积木。在位置(i, j)如果mask中第j位已经是1说明该位置已被占则移动到下一个位置(i, j1)。如果是0则我们可以选择不在此处放积木如果允许直接跳过。在此处放一块积木。但放积木必须匹配目标颜色。并且放置一块积木可能占据多个连续的位置比如1x2的积木。我们需要枚举所有可能的积木形状和放置方式题目会给定积木形状集合并检查 a. 放置后覆盖的所有格子在mask中都必须为0未被占用。 b. 放置的积木颜色必须与目标网格中对应格子的颜色一致对于单色积木就是所有覆盖格子颜色相同且与积木颜色匹配对于多色积木则需要完全匹配目标颜色图案。轮廓推进当一行的所有列都处理完后j移动到W我们就移动到下一行i1并且新的mask由上一行的放置情况决定实际上通常我们使用轮廓线DP经典的“插头”模型状态是当前处理格子和左侧、上方格子的连通情况但本题颜色是主要约束形状规则可能简化。对于“蓝桥杯18年国赛 搭积木”的具体版本积木很可能是高度为1、但长度可变占据连续多列的“长条”颜色是均匀的。这样问题就简化为如何用这些不同颜色、不同长度的长条去覆盖一个宽度为W、高度为H的网格使得覆盖后每个格子露出的颜色与目标一致并且覆盖过程满足“从底部连续向上”的规则。此时一个非常有效的状态定义是dp[i][mask]。i表示当前正在处理的行号从下往上0到H-1。mask是一个W位的二进制数表示当前行哪些列已经被之前行的积木“占据”或“支撑”到了当前高度。具体来说mask的第k位为1表示第k列在当前行i的位置已经被一个从下面延伸上来的积木占据了即该列的高度至少已经到了i因此我们不能在这个位置开始放置一个新的积木因为新积木需要从当前高度开始放置。mask为0的列表示该列在当前行是“空”的我们可以选择在这里开始放置一块新的积木。状态转移 从dp[i][mask]出发我们需要决策在第i行如何放置积木来填充那些mask中为0的列即空缺并使得放置后的颜色与目标第i行的颜色一致。我们可以枚举所有可能的积木长度L颜色C。对于每块积木我们枚举它在当前行所有可能的起始位置k要求从k开始的连续L列在mask中对应位都为0并且目标网格中第i行从k开始的L个格子的颜色都是C。如果满足条件我们就可以放置这块积木。放置后这些位置的“空缺”被填补状态mask中这些位需要被标记为1因为现在这些列的高度至少到了i并且被这块积木占据了。然后我们转移到dp[i][new_mask]。但是这里有一个关键当我们处理完第i行的所有可能放置后我们需要进入第i1行。那么第i1行的初始mask是什么应该是第i行放置结束后那些被积木覆盖的列其积木是否允许继续向上延伸如果积木高度大于1那么它会在下一行继续占据位置。因此mask实际上需要编码“哪些列被一个尚未结束的积木占据着”。这要求我们的状态还需要额外记录积木的“延续”信息。为了处理高度大于1的积木状态需要更复杂。一个经典技巧是将积木的放置视为一个“轮廓线”的填充过程。我们不再按行处理而是按“格子”处理使用轮廓线DP状态记录当前处理格子和其左侧、上方的格子是否属于同一个积木块以及该积木块的颜色。这就是“插头DP”模型复杂度较高。鉴于蓝桥杯国赛的难度和常见解法更可能的情况是积木的高度都是1但长度不同。这样问题就大大简化了变成了一个类似于“铺瓷砖”的问题但带有颜色约束。状态dp[i][mask]中i表示当前行mask表示上一行对当前行的“向下凸起”影响实际上因为高度为1上一行的积木不会延伸到本行所以mask可以只表示当前行哪些列已经被本行的积木覆盖了。我们逐行放置每一行内我们用积木去覆盖并且要匹配目标颜色。放置时积木必须连续覆盖一段区间并且区间内目标颜色相同。一行放置完后下一行的mask初始为0因为高度为1的积木不影响下一行。如果是这种情况那么dp[i][mask]的定义可以调整为dp[i][mask]表示已经正确覆盖了前i-1行并且第i行的覆盖情况为maskmask中1表示第i行该列已被覆盖0表示未覆盖的方案数。然后我们考虑第i行的放置如何由第i-1行转移过来。但由于高度为1行与行之间是独立的只有颜色匹配约束。实际上这变成了对每一行独立的“区间覆盖”问题最后将各行的方案数相乘即可。这似乎又太简单了不符合国赛压轴题的定位。综合多种信息我认为最符合“搭积木”描述和难度的模型是积木是高度为1、长度不等的长条但放置时必须从当前轮廓线的“底部”开始并且放置后该长条所覆盖的列其高度增加1。目标状态是一个二维颜色网格我们需要计算所有可能的放置顺序方案数。这等价于给定一个W x H的颜色矩阵我们要用若干种颜色的、长度不同的“矩形条”高度为1去覆盖它每个矩形条必须覆盖某一行的连续若干列并且覆盖区域的颜色必须一致。覆盖顺序必须满足每一列被覆盖的次数正好等于H即从下到上被H个矩形条覆盖并且从下到上的覆盖顺序其颜色序列必须等于目标矩阵该列的颜色序列。同时矩形条放置时必须放在当前“最低”的位置即从下往上逐行放置的感觉。这样一来问题就变成了一个带有颜色顺序约束的、按列相关的区间覆盖问题。这非常复杂。鉴于网上能找到的该题解法和讨论更常见的解法思路是预处理 状态压缩DP。核心步骤包括预处理所有可能的“放置操作”枚举每一块积木长度L颜色C以及它可以放置在哪些行区间因为高度为1所以行就是具体的某一行和列区间。但由于最终目标颜色矩阵的限制放置操作必须满足它所要覆盖的1 x L的格子颜色全部为C。所以我们可以扫描目标矩阵找出所有颜色相同的连续水平线段长度为L这就对应了一个可能的“放置操作”。记录这个操作在矩阵的特定位置放置一块颜色为C、长度为L的积木。定义DP状态dp[mask]表示已经执行了mask所代表的放置操作集合状态压缩mask的每一位对应一个预处理出的放置操作当前整个矩阵的覆盖情况。但这样状态数是指数级的2^操作数操作数可能很多不可行。优化因为放置必须从底部开始我们可以按行来划分阶段。定义dp[i][mask]表示已经覆盖了前i行即第0行到第i-1行并且当前第i行的覆盖状态为mask一个W位的二进制数表示第i行哪些列已经被覆盖。这里“覆盖”是指已经被某个积木占据。转移从dp[i][mask]出发我们要选择一些放置操作来覆盖第i行中尚未被覆盖的列mask中为0的位。这些放置操作必须1) 其覆盖的行区间包含第i行2) 其覆盖的列区间在当前mask下是未被覆盖的3) 放置后不能与已覆盖区域冲突。选择一组操作后得到新的覆盖状态new_mask对于第i行如果new_mask是全1即第i行被完全覆盖那么我们就可以转移到dp[i1][next_mask]其中next_mask表示第i1行被这些操作“延伸”影响后的状态如果操作的高度1它会覆盖多行。最终答案当i等于总行数H且所有行都被完全覆盖时dp[H][0]或类似状态即为方案数。这个DP过程已经相当复杂涉及状态压缩、预处理可行操作、行间转移等。这符合一道国赛压轴题的难度。5. 代码实现框架与关键技巧由于没有官方的确切题目描述和测试数据我无法给出完全准确的AC代码。但我可以基于上述最复杂的模型带颜色的行覆盖模型给出一个清晰的实现框架和关键技巧这足以应对此类问题的核心。#include bits/stdc.h using namespace std; // 假设参数 int H, W; // 网格高度和宽度 int n; // 积木种类数每种有颜色和长度 vectorint brick_len; // 积木长度 vectorchar brick_color; // 积木颜色 vectorstring target; // 目标颜色矩阵target[i][j] 表示第i行第j列的颜色 (i从下往上) // 预处理找出所有合法的放置操作 struct Operation { int r; // 起始行底行 int c; // 起始列最左列 int len; // 积木长度 char color; // 积木颜色 int mask; // 该操作覆盖的列掩码对于起始行r }; vectorOperation ops; void preprocess() { ops.clear(); // 枚举所有积木 for (int idx 0; idx n; idx) { int L brick_len[idx]; char C brick_color[idx]; // 枚举所有可能的起始位置 (r, c) for (int r 0; r H; r) { for (int c 0; c W - L; c) { // 检查从(r, c)开始的连续L格颜色是否都是C bool ok true; for (int k 0; k L; k) { if (target[r][c k] ! C) { ok false; break; } } if (ok) { Operation op; op.r r; op.c c; op.len L; op.color C; op.mask 0; for (int k 0; k L; k) { op.mask | (1 (c k)); } ops.push_back(op); } } } } // 可能需要去重或排序这里省略 } // DP求解 long long solve() { preprocess(); int op_cnt ops.size(); // dp[i][mask]: 已经覆盖完前i行且第i行的覆盖状态为mask的方案数 vectorvectorlong long dp(H 1, vectorlong long(1 W, 0)); dp[0][0] 1; // 初始状态第0行虚拟行已覆盖覆盖状态为0 // 按行DP for (int i 0; i H; i) { // 预处理出所有起始行为i的操作 vectorOperation cur_ops; for (const auto op : ops) { if (op.r i) { cur_ops.push_back(op); } } int cur_op_cnt cur_ops.size(); // 枚举第i行的所有状态mask for (int mask 0; mask (1 W); mask) { if (dp[i][mask] 0) continue; // 使用DFS或枚举子集的方法选择若干操作来覆盖第i行中mask为0的位 // 这里简化假设每个操作独立且操作高度为1不延伸多行。 // 更复杂的情况需要递归枚举操作组合并检查是否完全覆盖了~mask的位置。 // 这是一个集合覆盖问题对于W10可以状态压缩枚举。 // 简化版假设我们只用一块积木覆盖一段连续区域。实际上需要枚举所有操作组合。 // 这里给出一个简化思路的伪代码 int uncovered (~mask) ((1 W) - 1); // 第i行未被覆盖的列 // 我们需要用cur_ops中的一些操作去覆盖uncovered中的所有1。 // 枚举所有操作子集代价太大。通常需要另外的DP。 // 例如定义 f[submask] 表示覆盖submask这个列子集的方案数。 vectorlong long f(1 W, 0); f[0] 1; for (const auto op : cur_ops) { if ((uncovered op.mask) ! op.mask) continue; // 操作只能覆盖未覆盖区域 for (int s uncovered; s; s (s - 1) uncovered) { if ((s op.mask) op.mask) { // 如果操作覆盖的列是s的子集 f[s] f[s ^ op.mask]; } } } // 现在 f[uncovered] 表示用当前行操作完全覆盖未覆盖区域的方案数对于固定的mask if (f[uncovered] 0) { // 完全覆盖后第i行的新状态就是全1mask | uncovered int new_mask mask | uncovered; // 由于假设操作高度为1下一行初始状态为0无延伸 dp[i 1][0] dp[i][mask] * f[uncovered]; } } } // 最终覆盖完所有H行且第H行没有遗留覆盖状态mask0的方案数即为答案 return dp[H][0]; } int main() { // 读取输入 H, W, n, brick_len, brick_color, target // ... long long ans solve(); cout ans endl; return 0; }关键技巧与注意事项状态压缩表示用二进制位表示每列的覆盖状态这是处理网格类状压DP的基石。W10时1W1024状态数量可行。预处理剪枝预处理出所有合法的“放置操作”至关重要。它直接将颜色约束和积木形状约束融合避免了在DP转移中反复检查大幅提升效率。行间转移与行内覆盖DP状态dp[i][mask]巧妙地将问题分解。i表示阶段行mask表示当前行的状态。转移时需要解决一个子问题给定当前行未覆盖的列集合uncovered用若干合法操作完全覆盖它有多少种方案这个子问题本身又是一个状压DP如代码中的f数组是“集合覆盖计数”问题。复杂度分析外层DP状态数为O(H * 2^W)内层对每个状态需要计算集合覆盖DP其复杂度约为O(3^W)枚举子集。总复杂度约为O(H * 3^W * op_cnt)在W10时3^1059049加上H和op_cnt需要仔细优化和剪枝才能通过。大数处理方案数可能非常大需要使用long long甚至高精度计算。去重与顺序我们的DP计算的是放置操作的“集合”而不是序列。但题目要求的是“搭建顺序”方案数。如果积木都是不同的那么每个操作集合对应了多种排列顺序。我们需要在DP中区分不同的积木个体。通常的解决方法是将积木视为不同的个体即使在颜色和长度相同的情况下。这样每个“放置操作”会与具体的积木ID绑定。预处理时对于每个积木生成其所有可能的放置操作。DP状态mask可以压缩积木的使用情况如果积木数量n20或者使用“轮廓线积木索引”的状态定义。6. 常见问题与调试心得在实际实现和调试此类复杂状压DP时以下几个坑点几乎一定会遇到状态定义模糊导致重复或遗漏这是最大的难点。务必精确理解dp[i][mask]中i和mask的确切含义。i是“已经完成的行数”还是“当前正在处理的行”mask是“当前行的覆盖状态”还是“下一行的初始覆盖状态”定义不同初始化和转移方程天差地别。建议在注释中用自然语言明确写出状态含义并用手动模拟小样例如2x2网格来验证。预处理操作遗漏或错误预处理生成的“合法操作”集合必须完备且正确。特别注意积木是否可以旋转题目通常规定不能旋转。操作是否必须完全在网格内检查边界条件。颜色匹配是否严格大小写敏感吗对于高度大于1的积木预处理操作时要考虑所有可能的起始位置和方向。行内覆盖DPf数组的转移错误计算用操作覆盖集合uncovered的方案数时要确保每个操作只使用一次并且操作之间不重叠。代码中if ((uncovered op.mask) ! op.mask) continue;这一行确保操作只覆盖未覆盖区域。转移时f[s] f[s ^ op.mask];是经典“背包”式转移表示在状态s中加入了操作op。要确保操作op是s的子集。顺序计数问题如果题目要求的是“操作序列”的方案数而你的DP计算的是“操作集合”的方案数那么答案需要乘以每个操作集合内部的全排列。但更稳妥的方法是在DP状态中记录已经使用了哪些积木使用状态压缩这样自然就计入了顺序。此时状态可能是dp[i][mask][used]但维度会爆炸。通常需要利用“按行处理”的性质将“used”状态转化为“当前行可用的操作集合”这需要对积木进行排序并规定放置顺序。性能优化O(H * 3^W)的复杂度在W10时边界。可以有以下优化预处理操作子集对于每一行预处理出所有能覆盖特定列集合submask的操作列表。使用滚动数组dp[i][mask]只依赖于dp[i-1][...]可以滚动优化空间。剪枝无效状态很多mask状态可能永远无法达到比如奇偶性约束可以在DP前预处理出所有可能的mask。调试方法小数据打表构造最小的非平凡样例如2x21-2种积木手动计算出所有方案然后与程序输出对比。输出中间状态在DP过程中打印出dp[i][mask]的值看看是否按预期转移。验证预处理打印出所有预处理得到的操作检查其位置、颜色、掩码是否正确。7. 总结与思维提升“搭积木”这道题之所以经典是因为它将一个看似简单的游戏升华到了一个需要综合运用预处理、状态压缩、动态规划、集合覆盖等多种高级技巧的复杂算法问题。它考察的不仅仅是编码能力更是问题抽象、模型构建和算法设计的综合实力。通过这道题我们可以深刻理解“状态压缩DP”的精髓将复杂的状态用一个整数通常是二进制表示从而将指数级的状态空间压缩到可接受的范围内进而应用动态规划。这里的“状态”可以是集合、轮廓、覆盖情况等任何需要记录的信息。对于备赛蓝桥杯或类似算法竞赛的选手我的建议是掌握经典模型这道题是“铺砖”类问题如POJ 2411的变种带有颜色约束。熟练掌握经典铺砖问题的轮廓线DP解法是解决此类问题的基础。练习抽象能力拿到题目后不要被表面描述迷惑。第一步永远是抽象有哪些元素规则是什么目标是什么数据范围暗示了什么算法从简单到复杂如果直接想最终解法困难可以先考虑简化问题比如所有积木颜色相同、长度固定为1等再逐步增加约束。重视预处理很多复杂问题的突破口在于有效的预处理将约束提前计算好能极大简化主算法逻辑。善用调试工具对于状压DP写出正确的代码往往比想出思路更难。耐心构造小样例使用调试器或打印中间变量是必不可少的环节。最后这道题的代码实现可能很长但思路清晰后剩下的就是耐心的编码和调试。它带给你的思维锻炼和算法提升远比AC一道题本身更有价值。当你成功AC的那一刻你会对“状态”、“转移”、“压缩”这些概念有焕然一新的认识。