摘要
在用户体验和界面设计中，颜色搭配是个绕不开的核心问题。而在 LeetCode 的一道经典题目「栅栏涂色」中，系统地将这个看似简单的“上色”问题转化为一道有趣的动态规划挑战。今天我们就用 Swift 带你一探这个问题背后的“涂色学”，并分析它的数学规律、代码实现以及实际意义。
描述
题目大意很简单：你要给一排 n 根栅栏涂色。你一共有 k 种颜色可以选择，但有一个限制条件：不能有超过两根相邻的栅栏使用同一种颜色。
你需要返回总共有多少种不同的涂色方法。
例子：
输入: n = 3, k = 2
输出: 6
解释:
可能的涂色方式如下：
1. 红 红 蓝
2. 红 蓝 红
3. 红 蓝 蓝
4. 蓝 蓝 红
5. 蓝 红 蓝
6. 蓝 红 红
题解答案（Swift）
这个题目是动态规划的典型题，我们需要考虑状态转移和子问题的划分。简单来说，我们要区分两种情况：
same: 最后两根栅栏颜色相同diff: 最后两根栅栏颜色不同
根据这两个状态，我们可以构造出一个高效的递推公式。
func numWays(_ n: Int, _ k: Int) -> Int {
if n == 0 { return 0 }
if n == 1 { return k }
var same = 0
var diff = k
var total = same + diff
for _ in 2...n {
same = diff
diff = total * (k - 1)
total = same + diff
}
return total
}
题解代码分析
动态规划核心思路
我们用 same 表示前两根栅栏颜色相同的方案数，diff 表示前两根颜色不同的方案数。总方案数就是这两者之和。
递推关系如下：
- 当前的
same = diff（因为如果前一轮是不同色的，当前这一轮就可以延续相同颜色） - 当前的
diff = total * (k - 1)（从上一个状态的所有组合中选择不同的颜色）
我们每轮都更新这两个变量，直到涂完 n 根栅栏。
初始条件
当
n = 1，只有k种可能。当
n = 2，我们可以有：- 相同颜色：
k（比如红红、蓝蓝） - 不同颜色：
k * (k - 1)（比如红蓝、蓝红）
- 相同颜色：
示例测试及结果
示例 1：
let result = numWays(3, 2)
print(result) // 输出: 6
这个结果就跟题目中的例子一致，一共 6 种组合。
示例 2：
let result = numWays(1, 3)
print(result) // 输出: 3
只有一根栅栏，那就直接从三种颜色里选一种。
示例 3：
let result = numWays(4, 3)
print(result) // 输出: 66
解释较复杂，但动态规划会自动帮你计算出来所有组合。
时间复杂度
- O(n)
我们遍历一遍从 2 到 n，所以时间复杂度是线性的。
空间复杂度
- O(1)
我们只用了几个变量，没有额外数组存储，空间复杂度为常数级。
总结
这个问题虽然看起来像是简单的排列组合，但真正下手的时候会发现，不加限制的排列很容易，但加了“不能超过两个相同颜色”的规则后就变得有点挑战性了。
动态规划的好处就是可以把问题拆成更小的部分，一步步向目标推进。在这题中，理解 same 和 diff 这两个状态是关键。
实际场景联系
想象你是个装修师傅，客户让你刷墙，说每面墙可以选择多种颜色，但不希望连续三面墙刷成一样的颜色（太单调了）。你要怎么安排？其实就是这道题！
或者你是个前端开发者，在设计界面时，需要生成用户界面卡片颜色的方案，同样不能让相邻部分颜色一致。解决方法也就是应用这种动态递推模型。