线性动态规划：粉刷栅栏（经典变种——最多允许相邻两个栅栏同色）

题目描述：
你有一个长度为 n 的栅栏，需要给它涂上颜色。有 k 种不同的颜色可供选择。要求栅栏中最多允许两个相邻的栅栏颜色相同（即不能出现三个或以上连续相同颜色的栅栏）。请问，有多少种不同的涂色方案？
注意：由于结果可能很大，通常要求对结果取模（例如 10^9 + 7）。

题目解释：
这是一个经典的动态规划问题，结合了状态机思想。关键限制是“不能出现连续三个相同颜色”，因此我们在设计状态时需要记录当前栅栏的颜色以及它是否已连续出现两次。

解题过程

步骤1：定义状态

我们定义两个动态规划数组：

• same[i]：表示涂到第 i 个栅栏时，第 i 个栅栏与第 i-1 个栅栏颜色相同的方案数。
• diff[i]：表示涂到第 i 个栅栏时，第 i 个栅栏与第 i-1 个栅栏颜色不同的方案数。

这样，总方案数 total[i] = same[i] + diff[i]。

步骤2：找出状态转移方程

我们需要考虑第 i 个栅栏的颜色如何从第 i-1 个栅栏的状态转移而来。

情况A：第 i 个与第 i-1 个颜色相同（same[i]）

• 要求：第 i-1 个不能已经连续两次相同（否则会形成三个连续相同）。
• 因此，只能从 diff[i-1] 转移而来。
• 转移方式：第 i 个选择与第 i-1 个相同的颜色，只有 1 种选择。
• 转移方程：

\[ same[i] = diff[i-1] \times 1 \]

情况B：第 i 个与第 i-1 个颜色不同（diff[i]）

• 可以从 same[i-1] 或 diff[i-1] 转移而来。
• 对于第 i 个栅栏，它有 k 种颜色可选，但要排除与第 i-1 个相同的颜色。
• 因此，有 k-1 种选择。
• 转移方程：

\[ diff[i] = (same[i-1] + diff[i-1]) \times (k-1) \]

步骤3：确定初始条件

当 n = 1（只有一个栅栏）时：

• same[1]：不存在“与前一个相同”的情况，所以 same[1] = 0。
• diff[1]：第一个栅栏可以涂任意 k 种颜色，所以 diff[1] = k。
• 总方案数：total[1] = k。

实际上，我们可以直接从 i = 2 开始递推，初始条件为：

• same[2] = k（第一个和第二个颜色相同，有 k 种选择）。
• diff[2] = k * (k-1)（第一个和第二个颜色不同，第一个有 k 种选择，第二个有 k-1 种）。

但为了递推统一，我们通常用 i=1 初始化：

\[same[1] = 0,\quad diff[1] = k \]

然后从 i = 2 开始用上述转移方程计算。

步骤4：递推计算

以 k = 3 为例：

• i = 1：same[1] = 0, diff[1] = 3
• i = 2：
  same[2] = diff[1] * 1 = 3
diff[2] = (same[1] + diff[1]) * (k-1) = (0+3)*2 = 6
  总方案数 total[2] = 3 + 6 = 9（验证：第一个有3种选择，第二个若与第一个相同有1种，不同有2种，总方案 = 3*(1+2)=9，正确）
• i = 3：
  same[3] = diff[2] = 6
diff[3] = (same[2] + diff[2]) * 2 = (3+6)*2 = 18
total[3] = 6 + 18 = 24

步骤5：算法实现（伪代码）

def numWays(n: int, k: int) -> int:
    if n == 0: return 0
    if n == 1: return k
    
    same, diff = 0, k
    for i in range(2, n+1):
        new_same = diff
        new_diff = (same + diff) * (k - 1)
        same, diff = new_same, new_diff
    
    return same + diff

时间复杂度：O(n)
空间复杂度：O(1)（仅用两个变量滚动）

步骤6：举例验证

例：n = 3, k = 2（只有两种颜色，比如红R和蓝B）
手动枚举所有有效方案（无连续三个相同）：

• 以RR开头：RRB
• 以RB开头：RBR、RBB
• 以BR开头：BRB、BRR
• 以BB开头：BBR
  总共6种。
  用递推验证：
  same[1]=0, diff[1]=2
same[2]=2, diff[2]=2
same[3]=2, diff[3]=(2+2)*1=4
total=2+4=6 ✔

步骤7：变种与扩展

1. 如果允许任意相邻相同，没有限制：方案数就是 k^n。
2. 如果完全不允许相邻相同：方案数是 k * (k-1)^(n-1)。
3. 如果限制连续相同不能超过 m 个：需要定义状态 dp[i][c] 表示涂到第 i 个栅栏且末尾连续相同颜色长度为 c 的方案数，转移时考虑是否增加连续长度或切换颜色。

总结

本题通过将状态分为“末尾两格相同”和“末尾两格不同”两类，巧妙地避免了连续三个相同的情况。核心在于：

• 状态定义要能区分是否已连续两次相同。
• 转移时，“相同”只能从“不同”转移；“不同”可以从任意状态转移，但有颜色选择限制。

这种“状态机DP”的思想在许多限制连续性的问题中非常有用（如股票问题中的冷冻期、打家劫舍中的相邻限制等）。