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

题目描述：
假设有n个栅栏柱需要粉刷，共有k种颜色。要求不能有超过两个相邻的栅栏柱颜色相同。计算共有多少种不同的粉刷方案。

解题过程：

1. 问题分析

• 我们有n个栅栏柱，编号从1到n
• 有k种不同的颜色可用
• 限制条件：不能出现三个连续相同颜色的栅栏柱
• 目标：计算所有满足条件的粉刷方案总数

2. 基础情况分析

• 当n=0时：没有栅栏柱，只有1种方案（不粉刷）
• 当n=1时：有k种方案（每个栅栏柱都可以用k种颜色中的任意一种）
• 当n=2时：有k×k种方案（第一个栅栏柱k种选择，第二个栅栏柱k种选择）

3. 状态定义
定义dp[i]表示粉刷前i个栅栏柱的方案总数。

但是这种简单的状态定义不够，因为我们需要区分最后两个栅栏柱的颜色是否相同。因此我们需要更精细的状态定义：

定义两个状态：

• same[i]：粉刷前i个栅栏柱，且第i个栅栏柱与第i-1个栅栏柱颜色相同的方案数
• diff[i]：粉刷前i个栅栏柱，且第i个栅栏柱与第i-1个栅栏柱颜色不同的方案数

那么总方案数：dp[i] = same[i] + diff[i]

4. 状态转移方程推导

对于diff[i]（第i个与第i-1个颜色不同）：

• 第i-1个栅栏柱有某种颜色
• 第i个栅栏柱有k-1种选择（不能与第i-1个相同）
• 无论第i-1个与第i-2个是否相同，只要第i个与第i-1个不同即可
• 因此：diff[i] = (same[i-1] + diff[i-1]) × (k-1) = dp[i-1] × (k-1)

对于same[i]（第i个与第i-1个颜色相同）：

• 第i个栅栏柱必须与第i-1个颜色相同
• 但第i-1个不能与第i-2个颜色相同（否则会有三个连续相同颜色）
• 因此第i-1个必须与第i-2个颜色不同
• 所以：same[i] = diff[i-1] × 1（只有1种颜色选择，必须与第i-1个相同）

5. 初始条件

• 当i=1时：

  • same[1] = 0（只有一个栅栏柱，没有"相同"的概念）
  • diff[1] = k（第一个栅栏柱有k种颜色选择）
  • dp[1] = k

• 当i=2时：

  • same[2] = diff[1] = k（第二个与第一个相同，有k种方案）
  • diff[2] = dp[1] × (k-1) = k × (k-1)
  • dp[2] = k + k×(k-1) = k²

6. 算法实现

def numWays(n, k):
    if n == 0:
        return 0
    if n == 1:
        return k
    
    same = [0] * (n + 1)
    diff = [0] * (n + 1)
    dp = [0] * (n + 1)
    
    # 初始化
    same[1] = 0
    diff[1] = k
    dp[1] = k
    
    same[2] = diff[1]  # k
    diff[2] = dp[1] * (k - 1)  # k * (k - 1)
    dp[2] = same[2] + diff[2]  # k²
    
    # 动态规划
    for i in range(3, n + 1):
        same[i] = diff[i - 1]  # 第i个与第i-1个相同，但第i-1个必须与第i-2个不同
        diff[i] = dp[i - 1] * (k - 1)  # 第i个与第i-1个不同
        dp[i] = same[i] + diff[i]
    
    return dp[n]

7. 空间优化
由于我们只需要前两个状态，可以优化空间复杂度到O(1)：

def numWays_optimized(n, k):
    if n == 0:
        return 0
    if n == 1:
        return k
    
    same_prev = 0
    diff_prev = k
    total_prev = k
    
    for i in range(2, n + 1):
        same_curr = diff_prev
        diff_curr = total_prev * (k - 1)
        total_curr = same_curr + diff_curr
        
        same_prev, diff_prev, total_prev = same_curr, diff_curr, total_curr
    
    return total_curr

8. 示例验证
以n=3, k=2为例：

• 初始：same_prev=0, diff_prev=2, total_prev=2
• i=2：same_curr=2, diff_curr=2, total_curr=4
• i=3：same_curr=2, diff_curr=4, total_curr=6
  验证：确实有6种有效方案（排除两个连续相同后再接一个相同的方案）

9. 时间复杂度分析

• 时间复杂度：O(n)，需要遍历n个栅栏柱
• 空间复杂度：优化后为O(1)，未优化为O(n)

这个问题的关键在于理解"不能有三个连续相同颜色"的限制条件，并通过same和diff两个状态来精确跟踪相邻栅栏柱的颜色关系。