区间动态规划例题：最小涂色次数问题（相邻颜色不同限制的最小染色成本，环形版本）

题目描述

你有一个环形排列的 \(n\) 个方块（编号 0 到 n-1，其中 0 和 n-1 相邻）。每个方块初始无色，你需要用 k 种颜色（1 到 k）给每个方块染色。染色规则如下：

1. 相邻的方块颜色不能相同（包括环形首尾相邻的方块）。
2. 染色成本：将第 i 个方块染成颜色 c 的成本为 cost[i][c]（cost[i][c] 表示第 i 个方块染成颜色 c 的成本）。
   你需要计算将所有方块染色且满足相邻颜色不同的最小总成本。
   如果无法完成染色（例如 k=1 且 n>2 时必然无法满足相邻颜色不同），返回 -1。

解题思路

这个问题是典型的“环形区间 DP”问题。
核心难点：环形结构导致首尾颜色相互制约。
解决技巧：固定首块的颜色，将环形转化为线性问题，对每种颜色分别求解。

状态定义：
设 \(dp[i][c]\) 表示考虑前 i 个方块（i 从 0 开始），并且第 i 个方块染成颜色 c 时的最小累计成本。

状态转移：
对于第 i 个方块（i ≥ 1），其颜色 c 不能与前一个方块的颜色相同，因此：

\[dp[i][c] = \min_{p \neq c} dp[i-1][p] + cost[i][c] \]

其中 p 是前一个方块的颜色。

环形处理：
由于首尾颜色不能相同，我们可以枚举第一个方块的颜色 first_color（1 到 k），然后对线性部分（方块 1 到 n-1）进行 DP。
注意：最后一个方块的颜色不能等于 first_color。

最终答案：
对每种 first_color 的枚举，计算对应的最小成本，再取所有枚举中的最小值。

逐步解法

步骤 1：边界情况处理

• 如果 n == 1，没有相邻限制，直接返回 min(cost[0][c])。
• 如果 k == 1 且 n > 1，则无法满足相邻颜色不同，返回 -1。
• 如果 k == 2 且 n 是奇数，环形染色也无法满足（因为环形相邻颜色交替需要偶数个方块才能首尾相同颜色不冲突）。实际上，对于 k=2 环形染色，当 n 是奇数时无解，返回 -1。

步骤 2：枚举首块颜色
假设我们固定第一个方块颜色为 fc（1 ≤ fc ≤ k）。
初始化 dp[0][fc] = cost[0][fc]，dp[0][其他颜色] = INF（不可行）。

步骤 3：线性 DP 计算
从 i = 1 到 n-1 依次计算：

1. 对当前 i 的每种颜色 c（1 到 k），

\[ dp[i][c] = \min_{p \neq c} dp[i-1][p] + cost[i][c] \]

这里 p 是前一个方块的颜色，p 从 1 到 k 但 p ≠ c。
2. 为了快速计算，可以在每次 i 时记录前一行 dp[i-1] 的最小值和次小值（因为 p ≠ c，如果最小值对应的颜色正好是 c，就取次小值）。

步骤 4：处理环形限制
在 i = n-1 时，除了 p ≠ c 外，还要满足 c ≠ fc（因为首尾相邻）。
因此在计算 dp[n-1][c] 时，如果 c == fc，则直接跳过（设置为 INF）。

步骤 5：获取当前枚举下的答案
在 dp[n-1] 中，取所有 c ≠ fc 的最小值，即为当前 fc 下的最小成本。

步骤 6：枚举所有 fc 并取最优
对每个 fc 重复步骤 2~5，取所有结果的最小值。

举例说明

假设 n=3, k=3，成本矩阵 cost 如下（行 i，列 c）：
cost[0] = [1, 2, 3]
cost[1] = [4, 5, 6]
cost[2] = [7, 8, 9]

枚举 fc=1：

• 初始化 dp[0][1]=1, dp[0][2]=∞, dp[0][3]=∞。
• i=1:
  c=1: dp[1][1] = min(dp[0][2], dp[0][3])+4 = ∞（不可行）
  c=2: dp[1][2] = min(dp[0][1], dp[0][3])+5 = 1+5=6
  c=3: dp[1][3] = min(dp[0][1], dp[0][2])+6 = 1+6=7
• i=2（末尾，且 c≠fc=1）：
  c=2: 前一个颜色 p ≠ 2，即 p=1 或 3，但 p=1 时 dp[1][1]=∞，所以只能 p=3，dp[1][3]=7，所以 dp[2][2]=7+8=15
  c=3: 前一个颜色 p ≠ 3，p=2 时 dp[1][2]=6，所以 dp[2][3]=6+9=15
• 末尾可行最小值：min(15,15)=15

枚举 fc=2 和 fc=3 同理，最后取最小成本。

复杂度分析

• 枚举首块颜色：O(k)
• 每个线性 DP：O(nk)，每次转移用最小值和次小值优化后是 O(k) 而不是 O(k²)，所以总复杂度 O(nk²) 可优化为 O(n*k)
• 总复杂度：O(k * n * k) = O(nk²) 或优化后 O(nk)
• 空间：O(k) 滚动数组

关键点

1. 环形转线性：通过固定首块颜色，化环形为线性。
2. 相邻颜色不同的转移：利用前一行最小值和次小值加速。
3. 环形限制体现在末尾颜色不能等于首块颜色。

核心代码框架（伪代码）

def minCost(cost):
    n = len(cost)
    k = len(cost[0])
    if n == 1: return min(cost[0])
    if k == 1: return -1
    if k == 2 and n % 2 == 1: return -1
    INF = 10**9
    ans = INF
    for fc in range(k):
        dp_prev = [INF] * k
        dp_prev[fc] = cost[0][fc]
        for i in range(1, n):
            dp_cur = [INF] * k
            # 求上一行最小值和次小值
            min1, min2 = INF, INF
            for c in range(k):
                if dp_prev[c] < min1:
                    min2 = min1
                    min1 = dp_prev[c]
                elif dp_prev[c] < min2:
                    min2 = dp_prev[c]
            for c in range(k):
                best = min1 if dp_prev[c] != min1 else min2
                if i == n-1 and c == fc:
                    continue
                dp_cur[c] = best + cost[i][c]
            dp_prev = dp_cur
        for c in range(k):
            if c != fc:
                ans = min(ans, dp_prev[c])
    return ans if ans < INF else -1