LeetCode 276. 栅栏涂色
目录
题目描述
题意分析
有
n根排成一行的栅栏柱，k种颜色可选，每根柱子必须涂一种颜色。唯一的限制是：不能出现连续三根颜色相同。问总共有多少种涂色方案。先把限制读准。它允许相邻两根同色，只禁止三根连着同色。等价的局部表述是：若第
i-1根和第i-2根同色，则第i根必须换色；除此之外第i根随便涂。这个表述很重要，因为它说明「当前能怎么涂」只取决于前两根的相对关系（同色还是异色），而不取决于它们具体是哪两种颜色。「不取决于具体颜色」这一点是全题的技术核心。它意味着方案数在
k种颜色之间是完全对称的，我们不必记录颜色本身，只需记录一个二值信息，状态空间因此从 $O(k)$ 压到 $O(1)$。求的是方案总数而不是某个最优方案，且方案之间有明显的「按位置逐根决策、后一根的合法性只依赖前面局部」的递推结构，同时不存在贪心可利用的单调性——这些信号合起来指向按位置递推的计数。
边界要分清三处。
n = 0时没有柱子，题目按 0 种方案处理。n = 1时限制根本无法触发，答案就是k。n = 2时限制仍不可能触发（只有两根），答案是 $k^2$，需要确认递推能自然算出这个值而不是靠特判。另有一个隐藏边界：
k = 1时只有一种颜色，n >= 3必然出现三连同色，答案应为 0；n = 1答案是 1，n = 2答案是 1。好的递推应该让k = 1自然落进主逻辑，因为转移里会出现k - 1 = 0这个因子把非法分支归零。
解法：动态规划状态转移
核心思路
限制只关心末尾是否已有两根同色，不需要记录具体颜色。把前 i 根的合法方案分成两个互斥状态：
same：最后两根颜色相同；different：最后两根颜色不同。新柱与上一根同色时，旧状态必须是
different，且颜色没有选择，所以newSame = different。新柱与上一根异色时，两种旧状态都可转移，并有k - 1种颜色可选，所以newDifferent = (same + different) × (k - 1)。初始处理一根柱子：
same = 0、different = k。循环不变量是：进入第 i 次转移前，两变量准确统计前i - 1根的两类合法方案。新值必须先分别计算再统一覆盖旧值。正确性说明：两状态互斥且覆盖所有合法涂法。上述转移枚举了新柱同色或异色的全部情况；同色只允许接在异色状态后，正好排除三连同色。由初值归纳到 n，
same + different即全部合法方案数。
解题步骤
n == 0时返回 0。- 初始化一根柱子的状态
same = 0、different = k。- 从第 2 根开始计算
newSame与newDifferent。- 两个新状态计算完成后再一起赋值。
- 返回两种末尾状态之和。
n = 3, k = 2时状态从(0,2)变为(2,2)，再变为(2,4)，答案为 6。k = 1时 n 为 1 或 2 的答案是 1，n 至少为 3 时答案自然变成 0。
代码实现
class Solution {
public int numWays(int n, int k) {
if (n == 0) {
return 0;
}
int same = 0;
int different = k;
for (int posts = 2; posts <= n; posts++) {
int newSame = different;
int newDifferent = (same + different) * (k - 1);
same = newSame;
different = newDifferent;
}
return same + different;
}
}
func numWays(n int, k int) int {
if n == 0 {
return 0
}
same, different := 0, k
for posts := 2; posts <= n; posts++ {
newSame := different
newDifferent := (same + different) * (k - 1)
same, different = newSame, newDifferent
}
return same + different
}
复杂度分析
- 时间复杂度：$O(n)$。每根柱子只进行常数次运算。
- 空间复杂度：$O(1)$。仅保留上一层的两个状态。
关键点总结
- 状态记录末两根的关系，而非具体颜色，利用了颜色之间的对称性。
- 同色状态只能从上一层异色状态转移，异色状态可来自全部合法方案。
- 两个新状态都依赖旧值，必须先计算完再覆盖。
n = 0、k = 1无需额外复杂分支，初值和转移可统一处理。
易错点总结
newSame = same + different：n = 3, k = 2会把 AAA、BBB 计入，错误返回 8。newDifferent乘 k 而非k - 1：把与上一根同色的选择也算入异色状态。- 先覆盖 same 再计算 different：后者读到本轮新值，状态层次混乱。
- 只返回一个状态：同色和异色两类都可能合法，答案必须相加。
- 漏掉
n = 0：会把初始化的 k 种一柱方案错误当作空栅栏答案。- 对
k = 1一律返回 0：一根或两根柱子仍各有一种合法涂法。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 单状态线性递推，用来对照理解本题为何必须拆成两个状态 |
| 198. 打家劫舍 | 中等 | 同样按位置递推且相邻受限，但求的是最大值而非计数，转移取 max 而非求和 |
| 213. 打家劫舍 II | 中等 | 首尾相接的环形约束，需要拆成两次线性 dp，考察边界耦合的处理 |
| 256. 粉刷房子 | 中等 | 颜色不再对称（每种颜色代价不同），状态必须按具体颜色展开成三维 |
| 265. 粉刷房子 II | 困难 |
k 种颜色下用「最小值 + 次小值」把每层转移从 $O(k^2)$ 优化到 $O(k)$ |
| 91. 解码方法 | 中等 | 同为计数 dp，但转移的合法性依赖字符内容，需要处理 0 带来的不可达状态 |
| 746. 使用最小花费爬楼梯 | 简单 | 两来源转移的最小化版本，重点在起点与终点的边界约定 |
| 1137. 第 N 个泰波那契数 | 简单 | 依赖前三层的滚动递推，练习多变量滚动时的赋值顺序 |