区间动态规划例题：最小涂色次数问题（环形版本） 题目描述 有一个环形栅栏由n个木桩组成，每个木桩需要涂上特定的颜色。给定一个长度为n的环形颜色数组colors，其中colors[ i ]表示第i个木桩的颜色。每次涂色操作可以选择一段连续的木桩，将它们涂成同一种颜色。但涂色会覆盖之前的颜色。问最少需要多少次涂色操作才能让所有木桩涂上目标颜色。 注意：由于是环形，第一个木桩和最后一个木桩是相邻的。 解题思路 这个问题是"奇怪的打印机"问题的环形版本。我们需要将环形问题转化为线性问题来处理。 关键步骤分析 环形转线性 ：由于是环形结构，我们可以通过破环成链的技巧，将原数组复制一份接在后面，形成长度为2n的线性数组。 状态定义 ：定义dp[ i][ j]表示完成区间[ i,j ]的木桩涂色所需的最小操作次数。 状态转移分析 ： 如果colors[ i] == colors[ j ]，那么我们可以先涂整个区间，再调整中间部分 否则，我们需要在区间内找到一个分割点k，将区间分为[ i,k]和[ k+1,j ]两部分 边界条件 ：单个木桩只需要1次操作。 详细解题过程 步骤1：问题转化 将环形数组colors复制一份：newColors = colors + colors 现在问题转化为在长度为2n的数组上，找到所有长度为n的区间中的最小涂色次数。 步骤2：状态定义 定义dp[ i][ j]：完成区间[ i,j ]涂色的最小操作次数。 步骤3：状态转移方程 当i == j时，dp[ i][ j ] = 1（单个木桩需要1次操作） 当colors[ i] == colors[ j ]时： dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) 因为如果两端颜色相同，我们可以用一次操作涂整个区间，或者利用另一端的扩展 当colors[ i] != colors[ j ]时： 我们需要在区间[ i,j]内找到一个分割点k(i ≤ k < j)： dp[ i][ j] = min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j ]) 步骤4：环形处理 对于环形问题，我们需要计算所有可能的起点： result = min(dp[ i][ i+n-1 ])，其中i从0到n-1 步骤5：算法实现 采用标准的区间DP遍历方式：按区间长度从小到大计算。 举例说明 假设colors = [ 1,2,1,2 ]（环形） 破环成链后：[ 1,2,1,2,1,2,1,2 ] 计算过程： 长度为1的区间：dp[ i][ i ] = 1 长度为2的区间： dp[ 0][ 1]：颜色不同，min(dp[ 0][ 0]+dp[ 1][ 1 ]) = 1+1 = 2 dp[ 1][ 2]：颜色不同，min(dp[ 1][ 1]+dp[ 2][ 2 ]) = 1+1 = 2 长度为3的区间： dp[ 0][ 2]：两端相同(1==1)，min(dp[ 1][ 2], dp[ 0][ 1 ]) = min(2,2) = 2 长度为4的区间（原环形长度）： 计算所有起点长度为4的区间，取最小值 最终得到最小涂色次数为2。 复杂度分析 时间复杂度：O(n³)，需要三重循环 空间复杂度：O(n²)，用于存储DP表 这个解法通过破环成链巧妙处理了环形结构，是区间DP处理环形问题的典型方法。