LeetCode 276. 栅栏涂色
题目描述
题意分析
给
n根依次排列的栅栏柱涂色，每根可以使用k种颜色中的一种，要求不能出现连续三根同色，求合法涂色方案总数。两根相邻柱子可以同色。判断下一根能否沿用上一根的颜色，只需要知道末尾已经连续出现了几根同色柱子。
解法：末尾状态递推
核心思路
[!blue]
将处理完当前柱子的合法方案分为两类：
same表示末尾同色段长度为 2，different表示末尾同色段长度为 1。后者在至少两根柱子时，也就是最后两根颜色不同；只有一根柱子时也归入这一类。新柱子与上一根同色时，颜色只有一种选择，而且旧方案只能来自
different。如果接在same后面，就会形成三根同色。因此newSame = different。新柱子与上一根不同色时，无论旧方案来自哪一类，都可以选择除上一根颜色外的任意一种，共
k-1种。因此newDifferent = (same + different) * (k-1)。不需要记录上一根具体是什么颜色，因为每种颜色对应的换色选择数都相同。两类新方案由最后一步是否换色区分，互不重叠，又覆盖全部合法涂色方式，所以处理完所有柱子后将两类数量相加即可。每一轮的两个新状态都依赖旧值，需要先一起算出，再覆盖旧变量。
第一根柱子有
k种选择，末尾同色段只能长为 1，因此初始化same = 0、different = k。从第二根起按转移计算，自然允许两根同色，并禁止继续接出第三根。
解题步骤
- 先处理代码中的
n == 0边界，返回 0。- 初始化第一根柱子的两类方案数：
same = 0、different = k。- 从第二根到第
n根，分别计算newSame和newDifferent。- 两个新值都计算完后，再更新
same和different。- 返回
same + different。只有一种颜色时，前两根仍可合法涂色，第三根开始两类方案数都变成 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+1)$，每根柱子只进行固定次数的状态转移。
- 空间复杂度：$O(1)$，只保留上一根结束后的两类数量和当前临时值。
关键点总结
[!green]
- 只需区分末尾同色段长度为 1 还是 2，不必保存全部历史颜色。
- 沿用颜色只能接在长度 1 的末尾段后面，换色则可以接在所有合法方案后面。
- 按最后一步是否换色分类，不重不漏，最终两类相加。
易错点总结
[!yellow]
- 同色延长也允许来自
same：会把连续三根同色的非法方案算进去。- 换色时乘以
k：包含了上一根的颜色，换色只有k-1种选择。- 计算一个新值后立刻覆盖旧值：另一个转移可能读到错误的当前轮状态，应先算完两个新值。
- 只返回一类状态：末尾同色和不同色都可能合法，答案需要相加。
- 只有一种颜色就直接判无解：一根或两根柱子仍有合法方案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 256. 粉刷房子 | 中等 | 粉刷房子禁止相邻同色，本题只禁止连续三根同色，因此要区分末尾两根同色与异色状态。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！