说实话第一次在题单里看到 Counting Towers 这个题名时我还以为又是一道“铺满 2×n 地板”的经典递推毕竟这种题在动态规划入门题单里太常见了。结果真正上手之后才发现它考的并不是简单的 f(n) f(n-1) f(n-2)而是一个典型的“状态机 DP”你不仅要记录已经处理到第几列还要额外记录当前列和上一列之间的高度关系。这个设计点一出来整道题的难度立刻就不一样了。如果你正在刷 Codeforces 或其他 OJ 的动态规划题单或者准备面试时怕遇到“状态设计”类的题目Counting Towers 值得认真做一遍。它不涉及复杂的数据结构也没有奇怪的边界讨论但它能很好地训练一件事如何从一堆看似自由的选择里提炼出真正必要的状态。这篇文章我会从题意拆解、状态转移、代码实现到常见坑点完整复盘一遍我的解题过程希望能帮你少走一点弯路。1. Counting Towers 的题意拆解先别急着写递推1.1 题目描述与第一反应题目给我们 n 列砖块的位置每一列都可以从地面往上搭建砖块有两种1×1 的小方块和 1×2 的长砖。长砖既可以竖直放让某一列直接长高两格也可以横着放同时覆盖相邻两列让两列在同一高度各加一格。问最终搭建出来的不同塔的方案数答案对 1e97 取模。我第一次看到这个描述时脑子里最先冒出的思路是“按高度一层一层考虑”每一行可以放若干 1×1也可以在一些地方放横着的 1×2然后逐行往上铺。但很快我就发现这条路走不通因为塔的高度没有给定如果直接按行枚举层数是无限的根本没法写递推。另一个自然的想法是仿照斐波那契那类铺砖题令 dp[i] 表示前 i 列全部“稳定”的方案数然后考虑最后一列怎么放。但问题在于最后一块砖如果横着放它会跨到第 i1 列去这样“前 i 列完成”这件事就说不清楚。也就是说单纯按列做一维递推信息量不够。1.2 关键观察相邻列高度差只需要关注 0 和 1真正让我豁然开朗的是下面这个观察在从左往右逐列构建的过程中我们不需要知道每一列到底有多高只需要知道当前列和上一列之间的“高度差”。而高度差的情况实际上只有两种是需要单独记录的当前列和上一列高度相同记为状态 0当前列比上一列高 1记为状态 1。为什么不是差 2、差 3因为水平放置的 1×2 砖一次只能跨越两列。如果某时刻相邻两列的高度差大于 1那么高出来的那些格子既不能被水平砖“带过去”又会导致后续列无法平稳对接。从构造角度看一个合法的塔轮廓相邻列的高度差始终不会超过 1。你可以简单理解为水平砖是唯一能把两列“焊”在一起的零件而它的尺寸决定了相邻列的台阶高度只能是一格。既然高度差只有 0 和 1 两种情况那么 DP 状态里就只需要给每一列额外带一个 0/1 的标记。这就是这道题“状态设计”的突破口把看似无限的高度信息压缩成一个有限的状态机。1.3 为什么不能用简单的 f(n) f(n-1) f(n-2)在理顺状态之前我先走了不少弯路其中一个典型的错误想法是把横着的 1×2 砖看成“占两列的一整块”于是猜测递推是 f(n) f(n-1) f(n-2)。这个公式在 2×n 铺砖问题里很常见但在这里行不通。原因在于Counting Towers 里同一列的高度是可以继续往上长的。横着的 1×2 砖并不是一个“终结块”它只是让两列在某一层齐头并进在那之后两列都还可以继续往上搭 1×1 或者竖砖。换句话说每一列是一个持续累积高度的过程而不是像二维铺砖那样每个格子放了就不能再放。这个区别决定了我们必须用“列与列的相对高度”来描述进度而不是用“还剩多少列没铺”。想明白了这一点之后后面的状态转移就顺理成章了。2. 状态设计与转移方程把状态机画出来2.1 定义 dp[i][0] 和 dp[i][1]我最终采用的状态定义是dp[i][0]前 i 列已经完成并且第 i 列和它左边的第 i-1 列处于同一高度的方案数。为了方便理解我把它叫“平顶状态”。dp[i][1]前 i 列已经完成并且第 i 列比第 i-1 列高 1 格的方案数我叫它“凸起状态”。注意这里“前 i 列已经完成”的意思是从第 1 列到第 i 列内部所有砖块都已经正确放置不会出现某个格子空着等下一列来补的情况。允许存在的只有可能从第 i 列伸向第 i1 列的那些水平砖但我们用状态的 0/1 把它们全部显式表达出来了如果第 i 列顶部是平的说明没有未完成的连接如果第 i 列比左边高一格说明这里刚好有一个台阶下一步需要用水平砖把这个台阶接到右边去。2.2 转移方程推导从 dp[i-1][0] 到 dp[i][0] 有两种方式一种是在第 i 列放一个 1×1让它和左边的最高层对齐另一种是在第 i 列放一个竖直的 1×2让该列在原有基础上直接长高两格但它和左列的高度差仍然保持为 0因为左列之前也是平的所以本质上两者都是在原来的高度上各自加高最终高度差还是 0。所以这一项贡献是 2 乘以 dp[i-1][0]。从 dp[i-1][1] 到 dp[i][0] 只有一种方式第 i-1 列比它左边高出一格那么第 i 列就要放一个横着的 1×2 砖把这个台阶补平。这个水平砖的左半嵌入第 i-1 列凸出的那个格子右半落在第 i 列对应的位置于是第 i 列和左边的高度差变成 0。这一项贡献是 dp[i-1][1]。因此dp[i][0] 2 * dp[i-1][0] dp[i-1][1]再来推 dp[i][1]。想让第 i 列最后比第 i-1 列高 1 格有两种前置情况。第一种是前 i-1 列处在平顶状态 dp[i-1][0]此时第 i 列可以放一个横着的 1×2 砖左半搭在第 i-1 列顶部右半落在第 i 列的某个格子上这样第 i 列就会比左列凸出一格。第二种是前 i-1 列已经是凸起状态 dp[i-1][1]说明第 i-1 列比它左边高了一格那么第 i 列可以再接一个水平砖把台阶继续向右平移最终第 i 列仍然比第 i-1 列高一格。所以dp[i][1] dp[i-1][0] dp[i-1][1]这两个转移式合在一起就是一个非常干净的状态机。注意这个状态机的特点是dp[i][1] 右边的两项加起来正好等于 dp[i][0] 减去 dp[i-1][0]所以两个状态之间存在很明显的内部关联写代码时不要把它当成完全独立的两个数组。2.3 初始值与边界初始状态需要单独处理第 1 列。当只有一列时它可以放一个 1×1 方块此时的塔是平顶的对应 dp[1][0] 1也可以放一个竖直的 1×2 砖让这一列直接高两格但相对于“虚拟的第 0 列”它算是凸出了一格对应 dp[1][1] 1。不过实际代码里我习惯把 dp[1][0] 设为 2、dp[1][1] 设为 1为什么因为第 1 列的“平顶”其实有两种来源放一个 1×1或者放一个竖着的 1×2竖直砖不会造成横向台阶因此从状态机的角度它依然是平顶。而“凸起”状态只有一种来源就是放一个向右伸出的水平砖等待第 2 列来补。这两种初始化方式会直接影响转移式里 2 倍系数是否合理所以宁可多花一分钟在纸上把初始状态写清楚也不要等到样例不过再回来猜。我这里采用的版本与下文代码一致dp[1][0] 2dp[1][1] 1。如果你按照某个题解初始化成别的值务必确认它的状态定义是否和我一样否则很容易出现“整体平移”式的错误。2.4 手动模拟 n1, 2, 3 来验证状态机任何 DP 写完都应该先用小数据把状态转移表完整跑一遍确认没有出现荒谬的负数或者突然变大得不合理的值。n1 时答案是 3也就是 dp[1][0] dp[1][1] 3。n2 时利用递推式dp[2][0] 2 * dp[1][0] dp[1][1] 2 * 2 1 5dp[2][1] dp[1][0] dp[1][1] 2 1 3总数为 5 3 8。n3 时继续dp[3][0] 2 * 5 3 13dp[3][1] 5 3 8总数为 13 8 21。这份数值表现很漂亮3、8、21恰好是斐波那契数列的偶数位项 F(4)、F(6)、F(8)。事实上可以证明 dp[n][0] F(2n-1)、dp[n][1] F(2n-2)总方案数 ans F(2n)。这个性质可以作为代码正确性的一个强校验同时也是一个很有意思的收尾彩蛋。3. 代码实现与优化从 O(n) 数组到滚动变量3.1 最朴素的数组版本状态转移只有两个数组直接开长度为 n1 的 vector 即可。注意数据范围如果 n 能到 1e6开两个 long long 数组没什么压力但如果你习惯用 int取模运算时一定要把中间结果转成 long long否则 2 * dp[i-1][0] 那一项在 dp 值接近 1e97 时会溢出 int。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long dp0(n 1, 0), dp1(n 1, 0); dp0[1] 2; dp1[1] 1; for (int i 2; i n; i) { dp0[i] (2 * dp0[i - 1] dp1[i - 1]) % MOD; dp1[i] (dp0[i - 1] dp1[i - 1]) % MOD; } cout (dp0[n] dp1[n]) % MOD \n; return 0; }这段代码就是朴素版。优点是直观、好调试适合刚学 DP 时对照状态转移表一步步看。缺点是当 n 很大时数组的 O(n) 空间虽然不算多但完全没有必要。3.2 滚动数组优化观察递推式可以发现dp[i] 只依赖 dp[i-1]所以用两个变量滚动更新就足够了。这也是面试中最常要求的优化点从 O(n) 空间压到 O(1)。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long dp0 2, dp1 1; // 对应 i1 for (int i 2; i n; i) { long long ndp0 (2 * dp0 dp1) % MOD; long long ndp1 (dp0 dp1) % MOD; dp0 ndp0; dp1 ndp1; } cout (dp0 dp1) % MOD \n; return 0; }这里有个细节值得注意不能用 dp0 (2 * dp0 dp1) % MOD 直接覆盖然后再用新的 dp0 去算 dp1因为 ndp1 依赖的是旧的 dp0。必须先算出两个新值再一起赋值。这种“临时变量交换”的错误在滚动数组优化里非常常见我至少见过三次有人把顺序写反。3.3 与斐波那契数列的关系一个可选的优美结论如果你把两张表继续写下去n 4: dp0 34, dp1 21, 总数 55n 5: dp0 89, dp1 55, 总数 144你会发现总数 3, 8, 21, 55, 144 正好是 F(4), F(6), F(8), F(10), F(12)。这其实不是偶然。由 dp0[i1] 2dp0[i] dp1[i] 和 dp1[i1] dp0[i] dp1[i] 两式相加得到dp0[i1] dp1[i1] 3dp0[i] 2dp1[i]而由 dp0[i] dp0[i] dp1[i] - dp1[i] 之类的恒等变换可以推出总数序列满足一个更简单的二阶递推。更直接的办法是验证总数序列 T(i) 满足T(i) 3 * T(i-1) - T(i-2)比如 T(3)21, T(2)8, T(4)55正好 55 3*21 - 8。这个递推和斐波那契偶数位的公式完全一致。实际做题时如果发现自己推出的 DP 结果能与某些已知数列吻合是一个很好的 sanity check。不过我不建议比赛时花太多时间去推这个闭式除非题目明确要求 n 达到 1e18 且需要用矩阵快速幂。如果真遇到超大 n由于 T(i) 满足二阶线性递推可以用 2×2 矩阵快速幂把复杂度降到 O(log n)本质上就是计算斐波那契数列的偶数位项。这个扩展留给有兴趣的读者自己验证核心代码就是把二阶递推写成矩阵[ T(i) ] [ 3 -1 ] * [ T(i-1) ] [ T(i-1) ] [ 1 0 ] [ T(i-2) ]注意矩阵里有负系数取模时要多加上 MOD 再取模避免产生负数。4. 常见问题与排查技巧我踩过的坑都在这4.1 取模时机不对导致溢出或答案错误很多初学者会在递推内部到处取模比如每一步都对 dp0、dp1、2*dp0 分别取模。这种做法本身不错但要特别小心 2 * dp0 这个乘法。当 dp0 已经是一个接近 1e97 的数时2 * dp0 约等于 2e9虽然还在 32 位有符号整数范围内但已经不保险了如果后面再加一个 dp1累计可能超过 2^31-1。所以要么全程用 long long要么在乘法前强制转换。我个人的习惯是所有参与运算的变量都用 long long最后一步统一 % MOD。这样代码最清晰也不容易在中间步骤漏掉取模。4.2 状态定义没统一初始化抄错这是最隐蔽的坑。网上关于 Counting Towers 的题解有很多种写法有的把 dp[1][0] 初始化为 1有的初始化为 2有的把状态 1 定义成“当前列比前一列矮 1”还有的定义成“当前列有一个向右伸出的半块”。这些写法在各自的状态机里都是自洽的但如果你只抄转移式、不抄状态定义很容易出现“左边初始化是平顶 2右边转移系数却是 3”这种不匹配。建议你在本地写完代码后先用 n2 手动验证一遍。如果答案不是 8那大概率是初始值或者转移式里的系数出了问题。这时候不要急着乱试系数回到状态定义重新捋一遍当前状态到底代表什么从上一个状态到这个状态有哪几种放置方式每一步都说得清楚代码自然就对了。4.3 滚动数组覆盖顺序写反前面已经提到过一次这里单独列出来是因为它太典型了。滚动数组优化的核心是“先用旧值算新值再统一覆盖”。如果你写dp0 (2 * dp0 dp1) % MOD; dp1 (dp0 dp1) % MOD;那么第二个式子里的 dp0 已经是更新过的值算出来的 dp1 就会偏大。这类错误在样例比较小的时候特别难发现因为结果可能只是差一点点你不会立刻觉得“完全不对”。我的排查方法是把滚动数组优化前后的两份代码各跑一遍随机生成 n对拍一下一旦某个 n 的答案不一致就逐行对照转移式。4.4 从这道题学到的通用 DP 思路迁移Counting Towers 最值得记住的一点不是那个具体的转移式而是“压缩状态”的思维方式。很多计数题表面上看起来状态无限比如高度、长度、数量但只要找到一个关键的“相对量”或“差值”就能把无限变成有限。比如这道题里的“相邻列高度差”本质上就是用一个布尔值来代替“高度”这个变量。类似的技巧在很多题里都会用到连续子数组的和可以用前缀和的差值表示树上的深度可以用父子关系表示序列的 LIS 可以用末尾元素的最小值表示。下次再遇到看起来状态很多的 DP先别急着开多维数组停下来想一想到底哪些信息是真正影响后续决策的哪些信息只是看起来重要、实际可以从其他信息推算出来就这道题而言如果你还想继续练手可以尝试几个变形加入 1×3 的砖块会怎么样状态会变多如果允许塔的高度为负方向延伸会怎么样显然不合法但这能帮你理解边界条件的作用如果要求所有列的高度最终必须相等呢这就退化成另一种铺砖问题了。每改一个条件状态设计都要重新调整这个过程对锻炼 DP 直觉非常有效。最后再分享一个小技巧做题时如果你发现自己的 dp 数组里某个状态值一直用不上或者某个转移总是乘以一个超过 2 的系数多半是状态定义有冗余或者题目里还有隐含条件没发现。Counting Towers 的转移系数都很小2 和 1这就是状态设计到位的一个信号。好的状态机转移必然是清晰、简单、可解释的。 
长河君 · 2026/10/23 7:49:39 · 阅读 1.2k Counting Towers 状态机DP题解：相邻列高度差压缩与递推优化
说实话第一次在题单里看到 Counting Towers 这个题名时我还以为又是一道“铺满 2×n 地板”的经典递推毕竟这种题在动态规划入门题单里太常见了。结果真正上手之后才发现它考的并不是简单的 f(n) f(n-1) f(n-2)而是一个典型的“状态机 DP”你不仅要记录已经处理到第几列还要额外记录当前列和上一列之间的高度关系。这个设计点一出来整道题的难度立刻就不一样了。如果你正在刷 Codeforces 或其他 OJ 的动态规划题单或者准备面试时怕遇到“状态设计”类的题目Counting Towers 值得认真做一遍。它不涉及复杂的数据结构也没有奇怪的边界讨论但它能很好地训练一件事如何从一堆看似自由的选择里提炼出真正必要的状态。这篇文章我会从题意拆解、状态转移、代码实现到常见坑点完整复盘一遍我的解题过程希望能帮你少走一点弯路。1. Counting Towers 的题意拆解先别急着写递推1.1 题目描述与第一反应题目给我们 n 列砖块的位置每一列都可以从地面往上搭建砖块有两种1×1 的小方块和 1×2 的长砖。长砖既可以竖直放让某一列直接长高两格也可以横着放同时覆盖相邻两列让两列在同一高度各加一格。问最终搭建出来的不同塔的方案数答案对 1e97 取模。我第一次看到这个描述时脑子里最先冒出的思路是“按高度一层一层考虑”每一行可以放若干 1×1也可以在一些地方放横着的 1×2然后逐行往上铺。但很快我就发现这条路走不通因为塔的高度没有给定如果直接按行枚举层数是无限的根本没法写递推。另一个自然的想法是仿照斐波那契那类铺砖题令 dp[i] 表示前 i 列全部“稳定”的方案数然后考虑最后一列怎么放。但问题在于最后一块砖如果横着放它会跨到第 i1 列去这样“前 i 列完成”这件事就说不清楚。也就是说单纯按列做一维递推信息量不够。1.2 关键观察相邻列高度差只需要关注 0 和 1真正让我豁然开朗的是下面这个观察在从左往右逐列构建的过程中我们不需要知道每一列到底有多高只需要知道当前列和上一列之间的“高度差”。而高度差的情况实际上只有两种是需要单独记录的当前列和上一列高度相同记为状态 0当前列比上一列高 1记为状态 1。为什么不是差 2、差 3因为水平放置的 1×2 砖一次只能跨越两列。如果某时刻相邻两列的高度差大于 1那么高出来的那些格子既不能被水平砖“带过去”又会导致后续列无法平稳对接。从构造角度看一个合法的塔轮廓相邻列的高度差始终不会超过 1。你可以简单理解为水平砖是唯一能把两列“焊”在一起的零件而它的尺寸决定了相邻列的台阶高度只能是一格。既然高度差只有 0 和 1 两种情况那么 DP 状态里就只需要给每一列额外带一个 0/1 的标记。这就是这道题“状态设计”的突破口把看似无限的高度信息压缩成一个有限的状态机。1.3 为什么不能用简单的 f(n) f(n-1) f(n-2)在理顺状态之前我先走了不少弯路其中一个典型的错误想法是把横着的 1×2 砖看成“占两列的一整块”于是猜测递推是 f(n) f(n-1) f(n-2)。这个公式在 2×n 铺砖问题里很常见但在这里行不通。原因在于Counting Towers 里同一列的高度是可以继续往上长的。横着的 1×2 砖并不是一个“终结块”它只是让两列在某一层齐头并进在那之后两列都还可以继续往上搭 1×1 或者竖砖。换句话说每一列是一个持续累积高度的过程而不是像二维铺砖那样每个格子放了就不能再放。这个区别决定了我们必须用“列与列的相对高度”来描述进度而不是用“还剩多少列没铺”。想明白了这一点之后后面的状态转移就顺理成章了。2. 状态设计与转移方程把状态机画出来2.1 定义 dp[i][0] 和 dp[i][1]我最终采用的状态定义是dp[i][0]前 i 列已经完成并且第 i 列和它左边的第 i-1 列处于同一高度的方案数。为了方便理解我把它叫“平顶状态”。dp[i][1]前 i 列已经完成并且第 i 列比第 i-1 列高 1 格的方案数我叫它“凸起状态”。注意这里“前 i 列已经完成”的意思是从第 1 列到第 i 列内部所有砖块都已经正确放置不会出现某个格子空着等下一列来补的情况。允许存在的只有可能从第 i 列伸向第 i1 列的那些水平砖但我们用状态的 0/1 把它们全部显式表达出来了如果第 i 列顶部是平的说明没有未完成的连接如果第 i 列比左边高一格说明这里刚好有一个台阶下一步需要用水平砖把这个台阶接到右边去。2.2 转移方程推导从 dp[i-1][0] 到 dp[i][0] 有两种方式一种是在第 i 列放一个 1×1让它和左边的最高层对齐另一种是在第 i 列放一个竖直的 1×2让该列在原有基础上直接长高两格但它和左列的高度差仍然保持为 0因为左列之前也是平的所以本质上两者都是在原来的高度上各自加高最终高度差还是 0。所以这一项贡献是 2 乘以 dp[i-1][0]。从 dp[i-1][1] 到 dp[i][0] 只有一种方式第 i-1 列比它左边高出一格那么第 i 列就要放一个横着的 1×2 砖把这个台阶补平。这个水平砖的左半嵌入第 i-1 列凸出的那个格子右半落在第 i 列对应的位置于是第 i 列和左边的高度差变成 0。这一项贡献是 dp[i-1][1]。因此dp[i][0] 2 * dp[i-1][0] dp[i-1][1]再来推 dp[i][1]。想让第 i 列最后比第 i-1 列高 1 格有两种前置情况。第一种是前 i-1 列处在平顶状态 dp[i-1][0]此时第 i 列可以放一个横着的 1×2 砖左半搭在第 i-1 列顶部右半落在第 i 列的某个格子上这样第 i 列就会比左列凸出一格。第二种是前 i-1 列已经是凸起状态 dp[i-1][1]说明第 i-1 列比它左边高了一格那么第 i 列可以再接一个水平砖把台阶继续向右平移最终第 i 列仍然比第 i-1 列高一格。所以dp[i][1] dp[i-1][0] dp[i-1][1]这两个转移式合在一起就是一个非常干净的状态机。注意这个状态机的特点是dp[i][1] 右边的两项加起来正好等于 dp[i][0] 减去 dp[i-1][0]所以两个状态之间存在很明显的内部关联写代码时不要把它当成完全独立的两个数组。2.3 初始值与边界初始状态需要单独处理第 1 列。当只有一列时它可以放一个 1×1 方块此时的塔是平顶的对应 dp[1][0] 1也可以放一个竖直的 1×2 砖让这一列直接高两格但相对于“虚拟的第 0 列”它算是凸出了一格对应 dp[1][1] 1。不过实际代码里我习惯把 dp[1][0] 设为 2、dp[1][1] 设为 1为什么因为第 1 列的“平顶”其实有两种来源放一个 1×1或者放一个竖着的 1×2竖直砖不会造成横向台阶因此从状态机的角度它依然是平顶。而“凸起”状态只有一种来源就是放一个向右伸出的水平砖等待第 2 列来补。这两种初始化方式会直接影响转移式里 2 倍系数是否合理所以宁可多花一分钟在纸上把初始状态写清楚也不要等到样例不过再回来猜。我这里采用的版本与下文代码一致dp[1][0] 2dp[1][1] 1。如果你按照某个题解初始化成别的值务必确认它的状态定义是否和我一样否则很容易出现“整体平移”式的错误。2.4 手动模拟 n1, 2, 3 来验证状态机任何 DP 写完都应该先用小数据把状态转移表完整跑一遍确认没有出现荒谬的负数或者突然变大得不合理的值。n1 时答案是 3也就是 dp[1][0] dp[1][1] 3。n2 时利用递推式dp[2][0] 2 * dp[1][0] dp[1][1] 2 * 2 1 5dp[2][1] dp[1][0] dp[1][1] 2 1 3总数为 5 3 8。n3 时继续dp[3][0] 2 * 5 3 13dp[3][1] 5 3 8总数为 13 8 21。这份数值表现很漂亮3、8、21恰好是斐波那契数列的偶数位项 F(4)、F(6)、F(8)。事实上可以证明 dp[n][0] F(2n-1)、dp[n][1] F(2n-2)总方案数 ans F(2n)。这个性质可以作为代码正确性的一个强校验同时也是一个很有意思的收尾彩蛋。3. 代码实现与优化从 O(n) 数组到滚动变量3.1 最朴素的数组版本状态转移只有两个数组直接开长度为 n1 的 vector 即可。注意数据范围如果 n 能到 1e6开两个 long long 数组没什么压力但如果你习惯用 int取模运算时一定要把中间结果转成 long long否则 2 * dp[i-1][0] 那一项在 dp 值接近 1e97 时会溢出 int。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long dp0(n 1, 0), dp1(n 1, 0); dp0[1] 2; dp1[1] 1; for (int i 2; i n; i) { dp0[i] (2 * dp0[i - 1] dp1[i - 1]) % MOD; dp1[i] (dp0[i - 1] dp1[i - 1]) % MOD; } cout (dp0[n] dp1[n]) % MOD \n; return 0; }这段代码就是朴素版。优点是直观、好调试适合刚学 DP 时对照状态转移表一步步看。缺点是当 n 很大时数组的 O(n) 空间虽然不算多但完全没有必要。3.2 滚动数组优化观察递推式可以发现dp[i] 只依赖 dp[i-1]所以用两个变量滚动更新就足够了。这也是面试中最常要求的优化点从 O(n) 空间压到 O(1)。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long dp0 2, dp1 1; // 对应 i1 for (int i 2; i n; i) { long long ndp0 (2 * dp0 dp1) % MOD; long long ndp1 (dp0 dp1) % MOD; dp0 ndp0; dp1 ndp1; } cout (dp0 dp1) % MOD \n; return 0; }这里有个细节值得注意不能用 dp0 (2 * dp0 dp1) % MOD 直接覆盖然后再用新的 dp0 去算 dp1因为 ndp1 依赖的是旧的 dp0。必须先算出两个新值再一起赋值。这种“临时变量交换”的错误在滚动数组优化里非常常见我至少见过三次有人把顺序写反。3.3 与斐波那契数列的关系一个可选的优美结论如果你把两张表继续写下去n 4: dp0 34, dp1 21, 总数 55n 5: dp0 89, dp1 55, 总数 144你会发现总数 3, 8, 21, 55, 144 正好是 F(4), F(6), F(8), F(10), F(12)。这其实不是偶然。由 dp0[i1] 2dp0[i] dp1[i] 和 dp1[i1] dp0[i] dp1[i] 两式相加得到dp0[i1] dp1[i1] 3dp0[i] 2dp1[i]而由 dp0[i] dp0[i] dp1[i] - dp1[i] 之类的恒等变换可以推出总数序列满足一个更简单的二阶递推。更直接的办法是验证总数序列 T(i) 满足T(i) 3 * T(i-1) - T(i-2)比如 T(3)21, T(2)8, T(4)55正好 55 3*21 - 8。这个递推和斐波那契偶数位的公式完全一致。实际做题时如果发现自己推出的 DP 结果能与某些已知数列吻合是一个很好的 sanity check。不过我不建议比赛时花太多时间去推这个闭式除非题目明确要求 n 达到 1e18 且需要用矩阵快速幂。如果真遇到超大 n由于 T(i) 满足二阶线性递推可以用 2×2 矩阵快速幂把复杂度降到 O(log n)本质上就是计算斐波那契数列的偶数位项。这个扩展留给有兴趣的读者自己验证核心代码就是把二阶递推写成矩阵[ T(i) ] [ 3 -1 ] * [ T(i-1) ] [ T(i-1) ] [ 1 0 ] [ T(i-2) ]注意矩阵里有负系数取模时要多加上 MOD 再取模避免产生负数。4. 常见问题与排查技巧我踩过的坑都在这4.1 取模时机不对导致溢出或答案错误很多初学者会在递推内部到处取模比如每一步都对 dp0、dp1、2*dp0 分别取模。这种做法本身不错但要特别小心 2 * dp0 这个乘法。当 dp0 已经是一个接近 1e97 的数时2 * dp0 约等于 2e9虽然还在 32 位有符号整数范围内但已经不保险了如果后面再加一个 dp1累计可能超过 2^31-1。所以要么全程用 long long要么在乘法前强制转换。我个人的习惯是所有参与运算的变量都用 long long最后一步统一 % MOD。这样代码最清晰也不容易在中间步骤漏掉取模。4.2 状态定义没统一初始化抄错这是最隐蔽的坑。网上关于 Counting Towers 的题解有很多种写法有的把 dp[1][0] 初始化为 1有的初始化为 2有的把状态 1 定义成“当前列比前一列矮 1”还有的定义成“当前列有一个向右伸出的半块”。这些写法在各自的状态机里都是自洽的但如果你只抄转移式、不抄状态定义很容易出现“左边初始化是平顶 2右边转移系数却是 3”这种不匹配。建议你在本地写完代码后先用 n2 手动验证一遍。如果答案不是 8那大概率是初始值或者转移式里的系数出了问题。这时候不要急着乱试系数回到状态定义重新捋一遍当前状态到底代表什么从上一个状态到这个状态有哪几种放置方式每一步都说得清楚代码自然就对了。4.3 滚动数组覆盖顺序写反前面已经提到过一次这里单独列出来是因为它太典型了。滚动数组优化的核心是“先用旧值算新值再统一覆盖”。如果你写dp0 (2 * dp0 dp1) % MOD; dp1 (dp0 dp1) % MOD;那么第二个式子里的 dp0 已经是更新过的值算出来的 dp1 就会偏大。这类错误在样例比较小的时候特别难发现因为结果可能只是差一点点你不会立刻觉得“完全不对”。我的排查方法是把滚动数组优化前后的两份代码各跑一遍随机生成 n对拍一下一旦某个 n 的答案不一致就逐行对照转移式。4.4 从这道题学到的通用 DP 思路迁移Counting Towers 最值得记住的一点不是那个具体的转移式而是“压缩状态”的思维方式。很多计数题表面上看起来状态无限比如高度、长度、数量但只要找到一个关键的“相对量”或“差值”就能把无限变成有限。比如这道题里的“相邻列高度差”本质上就是用一个布尔值来代替“高度”这个变量。类似的技巧在很多题里都会用到连续子数组的和可以用前缀和的差值表示树上的深度可以用父子关系表示序列的 LIS 可以用末尾元素的最小值表示。下次再遇到看起来状态很多的 DP先别急着开多维数组停下来想一想到底哪些信息是真正影响后续决策的哪些信息只是看起来重要、实际可以从其他信息推算出来就这道题而言如果你还想继续练手可以尝试几个变形加入 1×3 的砖块会怎么样状态会变多如果允许塔的高度为负方向延伸会怎么样显然不合法但这能帮你理解边界条件的作用如果要求所有列的高度最终必须相等呢这就退化成另一种铺砖问题了。每改一个条件状态设计都要重新调整这个过程对锻炼 DP 直觉非常有效。最后再分享一个小技巧做题时如果你发现自己的 dp 数组里某个状态值一直用不上或者某个转移总是乘以一个超过 2 的系数多半是状态定义有冗余或者题目里还有隐含条件没发现。Counting Towers 的转移系数都很小2 和 1这就是状态设计到位的一个信号。好的状态机转移必然是清晰、简单、可解释的。