说实话，第一次在题单里看到 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 的长砖。长砖既可以竖直放（让某一列直接长高两格），也可以横着放（同时覆盖相邻两列，让两列在同一高度各加一格）。问最终搭建出来的不同塔的方案数，答案对 1e9+7 取模。
我第一次看到这个描述时，脑子里最先冒出的思路是“按高度一层一层考虑”：每一行可以放若干 1×1，也可以在一些地方放横着的 1×2，然后逐行往上铺。但很快我就发现这条路走不通，因为塔的高度没有给定，如果直接按行枚举，层数是无限的，根本没法写递推。
另一个自然的想法是仿照斐波那契那类铺砖题，令 dp[i] 表示前 i 列全部“稳定”的方案数，然后考虑最后一列怎么放。但问题在于，最后一块砖如果横着放，它会跨到第 i+1 列去，这样“前 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 列伸向第 i+1 列的那些水平砖，但我们用状态的 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] = 2，dp[1][1] = 1。如果你按照某个题解初始化成别的值，务必确认它的状态定义是否和我一样，否则很容易出现“整体平移”式的错误。
2.4 手动模拟 n=1, 2, 3 来验证状态机
任何 DP 写完，都应该先用小数据把状态转移表完整跑一遍，确认没有出现荒谬的负数或者突然变大得不合理的值。n=1 时答案是 3，也就是 dp[1][0] + dp[1][1] = 3。
n=2 时，利用递推式：
dp[2][0] = 2 * dp[1][0] + dp[1][1] = 2 * 2 + 1 = 5
dp[2][1] = dp[1][0] + dp[1][1] = 2 + 1 = 3
总数为 5 + 3 = 8。
n=3 时继续：
dp[3][0] = 2 * 5 + 3 = 13
dp[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 最朴素的数组版本
状态转移只有两个数组，直接开长度为 n+1 的 vector 即可。注意数据范围，如果 n 能到 1e6，开两个 long long 数组没什么压力；但如果你习惯用 int，取模运算时一定要把中间结果转成 long long，否则 2 * dp[i-1][0] 那一项在 dp 值接近 1e9+7 时会溢出 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; vector<long 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; // 对应 i=1 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, 总数 55
n = 5: dp0 = 89, dp1 = 55, 总数 144
你会发现总数 3, 8, 21, 55, 144 正好是 F(4), F(6), F(8), F(10), F(12)。这其实不是偶然。由 dp0[i+1] = 2dp0[i] + dp1[i] 和 dp1[i+1] = dp0[i] + dp1[i] 两式相加，得到：
dp0[i+1] + dp1[i+1] = 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 已经是一个接近 1e9+7 的数时，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”这种不匹配。
建议你在本地写完代码后，先用 n=2 手动验证一遍。如果答案不是 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），这就是状态设计到位的一个信号。好的状态机，转移必然是清晰、简单、可解释的。
