区间动态规划例题：最小涂色次数问题（相邻段颜色可相同但代价不同，且可任意染色分段）
题目描述
给定一个长度为 n 的空白序列（例如一排栅栏），你需要将其涂上颜色。共有 k 种不同的颜色可用。将序列涂色的规则是：
- 你可以将整个序列分成若干个连续的“段”来分别涂色。
- 每一段必须涂成同一种颜色。
- 相邻的两段可以涂成相同的颜色，也可以涂成不同的颜色。
涂色的成本由两部分组成：
- 分段成本：将长度为 L 的一段涂成单一颜色，无论颜色是什么，基础成本为 L（例如，每一米栅栏的涂刷材料成本固定）。
- 颜色切换成本：如果相邻的两段涂了不同的颜色，则会产生一个额外的切换成本 C（例如，更换油漆、清洗工具的成本）。如果颜色相同，则无此成本。
你的目标是找到涂色整个序列的最小总成本。
注意：你可以将序列分成任意数量的段（至少一段），并且可以选择每一段的颜色。
示例
n = 4, k = 3, C = 2
一种可能的涂色方案：分成两段，长度分别为 2 和 2。第一段涂颜色1，第二段涂颜色2。
总成本 = 第一段长度(2) + 第二段长度(2) + 颜色切换成本(2) = 6。
但这不是最优的。最优方案可能是分成一段，长度为4，涂颜色1。总成本 = 4（无切换成本）。所以最小总成本是4。
更复杂的示例
n = 5, k = 2, C = 1
最优方案可能是分成三段：长度分别为2, 2, 1。涂色为：颜色1, 颜色2, 颜色1。
总成本 = 2+2+1 + 切换成本(颜色1到颜色2:1) + 切换成本(颜色2到颜色1:1) = 5+2=7。
但也许分成两段：长度3和2，涂同一种颜色（比如颜色1）。
总成本 = 3+2 = 5，更优。
所以最小总成本是5。
解题过程
这个问题可以用区间动态规划解决。关键在于，当我们考虑一个区间时，它的涂色方案由其最后一段的颜色决定，因为这会影响到与下一段的切换成本。
1. 定义状态
设 dp[i][c] 表示：将序列的前 i 个单元（即长度为 i 的前缀）涂色完成，并且最后一段（即第 i 个单元所在的段）的颜色是 c 时的最小总成本。
这里 i 从 1 到 n，c 从 1 到 k。
2. 状态转移方程
我们想要计算 dp[i][c]。考虑最后一段是如何形成的。
最后一段的颜色固定是 c。假设最后一段的开始位置是 j（1 ≤ j ≤ i）。这意味着从位置 j 到位置 i 被涂成了同一种颜色 c，并且位置 j-1 要么不存在（即 j=1），要么是前一段的结尾，颜色是某种 c'。
那么，总成本可以分解为：
- 前 j-1 个单元的最小涂色成本，且其最后一段颜色是某个
c'。即dp[j-1][c']。注意，当 j=1 时，前面没有单元，我们定义dp[0][*] = 0。 - 新的一段（从 j 到 i）的长度是
(i - j + 1)，所以分段成本是(i - j + 1)。 - 如果 j > 1 且
c' != c，则需要加上颜色切换成本 C。如果c' = c或 j=1，则切换成本为0。
所以，对于每个可能的起始位置 j 和可能的前一段颜色 c'，我们可以计算出一个候选总成本：
cost = dp[j-1][c'] + (i - j + 1) + (如果 j>1 且 c' != c 则为 C，否则为0)
为了得到 dp[i][c]，我们需要在所有可能的 j (1到i) 和所有可能的 c' (1到k) 中选择最小的这个 cost。
但是，我们可以稍微优化这个计算。对于给定的 i 和 c，我们固定最后一段颜色为 c。当我们遍历 j 时，我们其实是在决定最后一段的长度。对于每个 j，我们需要知道前 j-1 个单元的最小成本，但需要根据其最后颜色 c' 是否等于 c 来考虑切换成本。
我们可以将前 j-1 个单元的最小成本分成两种情况：
- 情况A：前 j-1 个单元的最后颜色 等于 c。那么总成本是
dp[j-1][c] + (i - j + 1)。注意，没有切换成本。 - 情况B：前 j-1 个单元的最后颜色 不等于 c。那么我们需要找到前 j-1 个单元的最小成本，且最后颜色不是 c，然后加上切换成本 C 和分段成本。即
min_{c' != c} dp[j-1][c'] + (i - j + 1) + C。
因此，dp[i][c] 可以这样计算：
dp[i][c] = min_{j from 1 to i} {
min( dp[j-1][c], min_{c' != c} dp[j-1][c'] + C ) + (i - j + 1)
}
解释：对于每个分割点 j，前 j-1 个单元的最佳状态要么是最后颜色为 c（无切换成本），要么是其他颜色中最好的然后加切换成本 C。我们取这两种情况的较小值，然后加上新一段的成本 (i - j + 1)。
边界情况：当 j=1 时，dp[0][*] = 0，并且由于前面没有段，所以切换成本为0。此时 min( dp[0][c], min_{c' != c} dp[0][c'] + C ) 实际上就是 0，因为 dp[0][*] 都是0，两者相等。所以公式仍然适用。
3. 初始化
dp[0][c] = 0 对于所有颜色 c。这表示前0个单元（空序列）的成本是0，并且“最后颜色”可以是任意颜色（这是一个虚拟设定，方便计算）。
4. 计算顺序与优化
直接按照上述方程计算，时间复杂度是 O(n² * k)，因为对于每个 i 和 c，需要遍历 j 从1到i，并且对于每个 j 需要比较两种内部情况。而 min_{c' != c} dp[j-1][c'] 可以在遍历所有 c 时通过预处理来快速得到。
具体优化：对于每个固定的 j-1，我们可以预先计算出：
best_same[c] = dp[j-1][c]best_diff[c] = 所有 c' != c 中最小的 dp[j-1][c']
best_diff[c]可以通过先计算出全局最小值global_min = min_{c} dp[j-1][c]和次小值second_min来快速得到。如果对于某个颜色 c，dp[j-1][c] == global_min，则best_diff[c] = second_min，否则best_diff[c] = global_min。这样可以在 O(k) 时间内为所有 c 准备好best_diff[c]。
但即使如此，总的复杂度仍是 O(n² * k)。对于 n 和 k 不是特别大的情况（比如 n ≤ 2000, k ≤ 20），这是可以接受的。我们也可以进一步优化，但这里我们先按基础方法讲解。
5. 最终答案
完成所有计算后，整个序列（前 n 个单元）的最小总成本是：
min_{c = 1 to k} dp[n][c]
因为我们不关心最后一段是什么颜色，取所有可能颜色的最小值即可。
让我们用一个简单例子来演示
假设 n=3, k=2, C=1。
初始化：dp[0][1] = 0, dp[0][2] = 0。
计算 i=1：
对于每个颜色 c，遍历 j=1。
- c=1: j=1: 前0个单元，
min( dp[0][1], min_{c'!=1} dp[0][c']+C ) = min(0, 0+1) = 0。加上长度1，dp[1][1] = 0+1 = 1。 - c=2: 类似，
dp[1][2] = 1。
计算 i=2：
对于每个颜色 c，遍历 j=1 和 j=2。
- c=1:
- j=1: 前面没有，成本0，加上长度2，候选值=2。
- j=2: 前面是第一个单元。我们需要
min( dp[1][1], min_{c'!=1} dp[1][c']+C )。
dp[1][1]=1,dp[1][2]=1，所以min_{c'!=1} dp[1][c']+C = 1+1=2。取两者较小值：min(1,2)=1。加上长度1（从2到2），候选值=1+1=2。
比较 j=1 和 j=2 的候选值：min(2,2)=2。所以dp[2][1]=2。
- c=2: 对称计算，同样得到
dp[2][2]=2。
计算 i=3：
- c=1:
- j=1: 成本0 + 长度3 = 3。
- j=2: 前面是第一个单元。
min( dp[1][1], min_{c'!=1} dp[1][c']+C ) = min(1, 1+1=2) = 1。加上长度2 = 3。 - j=3: 前面是前两个单元。
min( dp[2][1], min_{c'!=1} dp[2][c']+C )。dp[2][1]=2,dp[2][2]=2，所以min_{c'!=1} dp[2][c']+C = 2+1=3。取较小值min(2,3)=2。加上长度1 = 3。
最小值是 min(3,3,3)=3。所以dp[3][1]=3。
- c=2: 对称，
dp[3][2]=3。
最终答案：min(dp[3][1], dp[3][2]) = 3。
验证：最优方案是分成一段，长度3，涂任意颜色，成本=3。符合预期。
总结
这个区间DP问题通过定义 dp[i][c] 状态，将问题分解为考虑最后一段的起点和颜色，从而能够处理分段成本和颜色切换成本。关键在于状态要记录最后一段的颜色，以便正确计算与下一段（在状态转移时是虚拟的下一段，实际上是在构建更长的前缀时考虑）的切换成本。