最小涂色次数问题（环形版本） 题目描述 给定一个环形字符串s，长度为n（环形意味着首尾字符相邻）。每次操作可以将任意连续的一段相同字符涂成另一种颜色（要求目标颜色与当前颜色不同）。你的目标是将整个环形字符串涂成同一种颜色，问最少需要多少次涂色操作？ 示例 输入：s = "AABAA" 环形示意图：A-A-B-A-A（首尾相连） 输出：1 解释：一种最优方案是将中间的B及其相邻区域一次涂色，但因为是环形，需要仔细分析区间。 解题思路 环形转线性 ：将环形字符串复制一份拼接成长度为2n的线性字符串，枚举每个起点长度为n的区间，转化为线性问题求解。 线性版本基础DP ：定义dp[ i][ j]表示将区间[ i, j ]涂成统一颜色的最少操作次数。 状态转移 ： 如果s[ i] == s[ j]，区间两端颜色相同，可以在涂色过程中利用同一操作覆盖两端，状态转移为dp[ i][ j] = dp[ i+1][ j-1 ] + 1？需谨慎，实际上若中间部分已涂好，两端颜色一致时可能减少操作。 更通用的转移：枚举分割点k，将区间分为[ i, k]和[ k+1, j ]，但需考虑两端颜色一致时的优化。 环形处理 ：对每个长度为n的线性区间计算dp值，取最小值作为答案。 详细步骤 将字符串s复制拼接成S = s + s，长度2n。 定义DP数组dp[ l][ r]表示将区间[ l, r ]涂成同色的最少操作次数。 初始化：单个字符无需涂色，dp[ i][ i ] = 0。 状态转移方程： 如果S[ l] == S[ r ]： dp[ l][ r] = min(dp[ l+1][ r], dp[ l][ r-1 ]) （因为两端同色，涂一端时可顺带覆盖另一端） 否则： dp[ l][ r] = min_ {l≤k<r} {dp[ l][ k] + dp[ k+1][ r ]} （枚举分割点，合并左右区间操作数） 遍历每个起点i（0≤i<n），计算线性区间[ i, i+n-1]的dp值，取最小值min(dp[ i][ i+n-1 ])作为答案。 示例推导 s = "AABAA" → S = "AABAAAABAA" 计算区间[ 0,4 ]： dp[ 0][ 4]：S[ 0]=A, S[ 4]=A，同色，转移为min(dp[ 1][ 4], dp[ 0][ 3 ]) 需先计算子区间，最终得到dp[ 0][ 4 ]=1（一次操作将B及周边涂成A）。 其他起点区间结果相同，故答案为1。 总结 本题通过环形转线性技巧，将问题分解为多个线性区间DP求解，关键点在于处理两端颜色相同时的优化转移，避免不必要的分割。时间复杂度O(n³)，可通过预处理优化枚举。