区间动态规划例题：最小涂色次数问题（环形版本进阶：分段染色最小成本） 题目描述 有一个环形序列，包含 n 个格子，每个格子需要被涂成某种颜色（颜色用整数表示，范围是 1 到 m ）。初始时，所有格子都是无色的（用 0 表示）。涂色规则如下： 每次操作可以选择一段连续的格子（在环形序列上连续的一段弧），将这段格子全部涂成同一种颜色。 如果某个格子已经被涂过色，再次涂色会覆盖之前的颜色。 目标是将所有格子涂成给定的目标颜色序列 target[0..n-1] （每个 target[i] 是 1 到 m 的整数）。 每次涂色的成本为 1，求完成目标的最小涂色次数。 注意：序列是环形的，即 target[n-1] 和 target[0] 是相邻的。 示例 输入： target = [1,2,1,2,1] 环形序列长度 n=5，颜色 1 和 2。 一种涂色方案： ① 将整个环涂成颜色1（成本1），得到 [ 1,1,1,1,1 ]； ② 选择一段连续格子涂成颜色2，比如从索引1到3（环形连续段，在环上看是连续的一段），得到 [ 1,2,2,2,1 ]； ③ 再将索引2的格子涂成颜色1（或者更高效的方式是选择一段只包含索引2的段），得到 [ 1,2,1,2,1 ]。 总成本为3。 是否存在成本更低的方案？可以思考。 解题思路 这个问题是经典的“奇怪打印机”问题的环形版本。在“奇怪打印机”中，我们有一个线性字符串，每次可以打印一段相同字符，打印会覆盖之前的内容，求最少打印次数。该问题可以用区间动态规划解决： 定义 dp[i][j] 表示将区间 [i, j] 涂成目标颜色所需的最少打印次数。转移时，考虑第一个字符 target[i] 的打印时间，可以单独打印，也可以与后面某个相同颜色的位置 k 一起打印，这样可以将区间分成两部分。 现在序列是环形的，我们可以将其转化为线性问题处理。常用技巧是“破环成链”：将原序列复制一份接在后面，得到一个长度为 2n 的序列。我们考虑所有长度为 n 的连续子段，对每个这样的子段求解线性版本的问题，取最小值作为答案。 步骤详解 步骤1：线性版本的状态定义 对于线性数组 a[0..n-1] ，定义 dp[i][j] 表示将子数组 a[i..j] 涂成目标颜色所需的最少操作次数。 其中 0 ≤ i ≤ j < n 。 步骤2：线性版本的状态转移 当 i == j 时，只需要一次操作： dp[i][j] = 1 。 当 i < j 时，考虑第一次涂色如何覆盖 a[i] ： 方案A：单独涂 a[i] ，然后处理剩下的区间 [i+1, j] ，此时成本为 1 + dp[i+1][j] 。 方案B：如果后面某个位置 k （ i < k ≤ j ）满足 a[i] == a[k] ，那么可以在同一次操作中将 a[i] 和 a[k] 一起涂（因为涂色是连续的一段，所以 a[i..k] 会被涂成同色，但中间可能还有其他颜色，不过可以在同一次操作中先涂成 a[i] 的颜色，然后再处理内部）。 实际上，更精确的转移是： 如果 a[i] == a[k] ，那么我们可以将区间 [i, k] 在第一次涂色中整体涂成 a[i] 的颜色，然后分别处理 [i+1, k-1] 和 [k+1, j] 。但注意，第一次涂色覆盖了 [i, k] 后， [i+1, k-1] 已经变成了 a[i] 的颜色，需要再调整成目标颜色，这可以在后续操作中完成。 因此，转移方程为： dp[i][j] = min( dp[i][j], dp[i+1][k-1] + dp[k][j] ) ，当 a[i] == a[k] 时。 这里 dp[k][j] 是因为 a[k] 已经在第一次涂色中被涂对，所以处理 [k, j] 即可，而 [i+1, k-1] 需要单独处理（但注意 a[i] 和 a[k] 颜色相同，所以 [i+1, k-1] 可以在 [i, k] 第一次涂色后自由处理）。 更常见的写法是： dp[i][j] = dp[i+1][j] + 1 作为初始值，然后如果 a[i] == a[k] ，则 dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]) ？不，这样不对，因为 a[i] 和 a[k] 同色，所以可以合并打印。 实际上标准“奇怪打印机”的转移是： dp[i][j] = dp[i+1][j] + 1 ， 然后对每个 k 从 i+1 到 j ，如果 a[i] == a[k] ，则 dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) 。 这里 dp[i+1][k-1] 是处理 (i, k) 中间部分， dp[k][j] 是处理从 k 到 j 的部分，而 a[i] 和 a[k] 在同一次打印中完成。 验证：当 k = i+1 时， dp[i+1][k-1] 为 0（空区间），所以 dp[i][j] = dp[k][j] ，这表示 a[i] 和 a[i+1] 一起打印，所以只需处理 [i+1, j] 但注意此时 a[i+1] 已经打印正确，所以只需处理 [i+2, j] ？这里要小心。 正确的理解是：打印 a[i] 时，可以延伸到 k ，这样区间 [i, k] 都变成 a[i] 的颜色，然后分别处理 [i+1, k-1] 和 [k+1, j] ，但 [i+1, k-1] 的目标颜色不一定是 a[i] ，所以需要额外步骤调整，这部分的最小步数就是 dp[i+1][k-1] 。而 [k, j] 中 a[k] 已经正确，所以只需处理 [k, j] ，即 dp[k][j] 。 但注意 [k, j] 的起点 k 的颜色已经是正确的，所以 dp[k][j] 表示从 k 到 j 的最小打印次数，且第一次打印可以不从 k 开始。 因此转移正确。 最终答案为 dp[0][n-1] 。 步骤3：环形版本的处理 将原数组 target 复制一份接到后面，得到长度为 2n 的数组 a 。 对每个起始点 s （ 0 ≤ s < n ），考虑线性区间 [s, s+n-1] ，计算其线性版本的最小打印次数，记为 linear_min(s) 。 则环形答案为 min{ linear_min(s) | s=0..n-1 } 。 注意 ：在环形中，由于是环，第一次涂色可以选择环上任意一段连续弧，这已经被“破环成链”后选择不同起点覆盖了。 步骤4：实现细节 线性版本用区间 DP 计算，区间长度从小到大。 注意当区间长度为 1 时， dp[i][i] = 1 。 在计算 dp[i][j] 时，先令 dp[i][j] = dp[i+1][j] + 1 ，然后枚举 k = i+1 到 j ，如果 a[i] == a[k] ，则 dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) 。 这里 dp[i+1][k-1] 当 k = i+1 时，区间为空，值为 0。 对于环形，对每个起点 s，取区间 [s, s+n-1] 的线性 DP 结果。 示例推导 以 target = [1,2,1,2,1] 为例，n=5。 破环成链 ：得到 a = [ 1,2,1,2,1,1,2,1,2,1 ]。 考虑起点 s=0，区间 [ 0,4 ] 即原序列。 线性 DP 表计算（区间长度 len 从 1 到 5）： len=1: dp[ i][ i ]=1。 len=2: [ 0,1]: 先 dp=dp[ 1][ 1]+1=2，然后检查 k=1，a[ 0]=1, a[ 1 ]=2 不同，所以 dp=2。 [ 1,2]: a[ 1]=2, a[ 2 ]=1 不同，dp=2。 [ 2,3 ]: 不同，dp=2。 [ 3,4 ]: 不同，dp=2。 len=3: [ 0,2]: 先 dp=dp[ 1][ 2]+1=2+1=3。检查 k=1: a[ 0]!=a[ 1]；k=2: a[ 0]==a[ 2]=1，则候选= dp[ 1][ 1]+dp[ 2][ 2 ]=1+1=2。所以 dp=2。 [ 1,3]: 先 dp=dp[ 2][ 3]+1=2+1=3。k=2: 不同；k=3: a[ 1]==a[ 3]=2，候选= dp[ 2][ 2]+dp[ 3][ 3 ]=1+1=2，所以 dp=2。 [ 2,4 ]: 类似，dp=2。 len=4: [ 0,3]: dp=dp[ 1][ 3]+1=2+1=3。k=1: 不同；k=2: a[ 0]==a[ 2]，候选= dp[ 1][ 1]+dp[ 2][ 3 ]=1+2=3；k=3: 不同。所以 dp=3。 [ 1,4]: dp=dp[ 2][ 4]+1=2+1=3。k=2: 不同；k=3: a[ 1]==a[ 3]，候选= dp[ 2][ 2]+dp[ 3][ 4 ]=1+2=3；k=4: 不同。所以 dp=3。 len=5: [ 0,4]: dp=dp[ 1][ 4 ]+1=3+1=4。 k=1: 不同；k=2: a[ 0]==a[ 2]，候选= dp[ 1][ 1]+dp[ 2][ 4]=1+2=3；k=3: 不同；k=4: a[ 0]==a[ 4]，候选= dp[ 1][ 3]+dp[ 4][ 4 ]=2+1=3。 所以 dp[ 0][ 4 ]=3。 因此起点 s=0 时，线性最少为 3。 再试起点 s=1，区间 [ 1,5] 即 [ 2,1,2,1,1 ]： 计算得 dp[ 1][ 5 ] 的最小打印次数。 手工快速推：可以先将整个区间涂成1（一次），然后涂 [ 1] 为2（一次），再涂 [ 3 ] 为2（一次），共3次。 实际上可能更优的方案是：先涂成2（一次），然后涂 [ 0,2,4] 为1（但这是环形起点不同，这里线性区间是 [ 2,1,2,1,1 ]），最优可能是3次。 我们不需要枚举所有起点，因为对称性，此例中所有起点结果都是3。 所以环形答案为 3。 算法复杂度 线性版本 DP：状态数 O(n²)，转移 O(n)，总 O(n³)。 环形：做 n 次线性 DP，总 O(n⁴) 可能太大。 优化：其实破环成链后，可以在 2n 的数组上直接做区间 DP，然后取所有长度为 n 的区间中的最小值。但标准做法是：在 2n 数组上做 DP，然后答案是 min{dp[s][s+n-1]} 。 DP 复杂度 O((2n)³)=O(8n³)，可接受（n 一般 ≤ 100）。 关键点总结 环形问题通过“破环成链”转为线性问题。 线性“奇怪打印机”问题的状态转移： dp[i][j] = min(dp[i+1][j]+1, min{dp[i+1][k-1] + dp[k][j] | a[i]==a[k]}) 。 最终取所有长度为 n 的区间的最小值。 这个问题的核心在于理解“一次涂色一段连续区间，覆盖旧颜色”的操作，以及如何利用区间 DP 合并相同颜色的打印。