线性动态规划：粉刷栅栏问题

题目描述

假设你有一个长度为 n 的栅栏，每个栅栏柱可以涂上 k 种颜色中的一种。要求栅栏中不能有超过两个相邻的栅栏柱颜色相同。给定栅栏长度 n 和颜色数 k，计算有多少种不同的涂色方案。

解题思路

这个问题可以用动态规划来解决。关键是要区分最后两个栅栏柱的颜色是否相同，因为这会影响到下一个栅栏柱的颜色选择。

详细步骤

步骤1：定义状态

我们定义两个状态：

• same[i]：表示长度为 i 的栅栏中，最后两个栅栏柱颜色相同的方案数
• diff[i]：表示长度为 i 的栅栏中，最后两个栅栏柱颜色不同的方案数

步骤2：确定初始状态

对于长度为1的栅栏：

• same[1] = 0（只有一个栅栏柱，不存在相邻情况）
• diff[1] = k（可以涂任意颜色）

对于长度为2的栅栏：

• same[2] = k（两个栅栏柱涂相同颜色）
• diff[2] = k × (k-1)（第一个有k种选择，第二个有k-1种不同颜色）

步骤3：状态转移方程

对于长度 i ≥ 3 的栅栏：

1. 最后两个颜色相同的情况 (same[i])：

   • 只能从 diff[i-1] 转移过来
   • 因为如果前两个已经相同，就不能再添加相同颜色
   • 转移：same[i] = diff[i-1] × 1（只能选择与前一个相同的颜色）

2. 最后两个颜色不同的情况 (diff[i])：

   • 可以从 same[i-1] 和 diff[i-1] 转移过来
   • 从 same[i-1] 转移：有 (k-1) 种选择（不能与倒数第二个相同）
   • 从 diff[i-1] 转移：有 (k-1) 种选择（不能与倒数第二个相同）
   • 转移：diff[i] = (same[i-1] + diff[i-1]) × (k-1)

步骤4：最终结果

总方案数 = same[n] + diff[n]

示例演示

假设 n = 3, k = 2（2种颜色，比如红和蓝）

手动计算验证：

• 有效方案：红蓝红、红蓝蓝、蓝红蓝、蓝红红（共4种）
• 无效方案：红红红、蓝蓝蓝（违反规则）

动态规划计算：

• same[1] = 0, diff[1] = 2
• same[2] = 2, diff[2] = 2 × 1 = 2
• same[3] = diff[2] = 2
• diff[3] = (same[2] + diff[2]) × 1 = (2 + 2) × 1 = 4
• 总方案数 = same[3] + diff[3] = 2 + 2 = 4 ✓

算法实现

def numWays(n: int, k: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return k
    
    same = [0] * (n + 1)
    diff = [0] * (n + 1)
    
    # 初始状态
    same[1] = 0
    diff[1] = k
    same[2] = k
    diff[2] = k * (k - 1)
    
    # 状态转移
    for i in range(3, n + 1):
        same[i] = diff[i - 1]  # 只能从diff转移，选择与前一个相同的颜色
        diff[i] = (same[i - 1] + diff[i - 1]) * (k - 1)
    
    return same[n] + diff[n]

复杂度分析

• 时间复杂度：O(n)，只需要遍历一次
• 空间复杂度：O(n)，可以使用两个变量优化到O(1)

关键点总结

1. 将问题分解为"最后两个颜色相同"和"最后两个颜色不同"两种情况
2. 理解状态转移的逻辑：相同颜色只能从不同颜色转移，不同颜色可以从两种情况转移
3. 注意边界条件的处理，特别是n=1和n=2的情况

这种方法通过巧妙的分类讨论，将复杂的约束条件转化为简单的状态转移，是动态规划解决约束计数问题的典型范例。