区间动态规划例题：最小涂色次数问题（环形版本） 题目描述 你有一个环形栅栏，由 n 个木桩组成，编号从 0 到 n-1 。每个木桩需要涂成特定的颜色，用一个字符串 colors 表示，其中 colors[i] 是第 i 个木桩的颜色。涂色规则如下：每次涂色可以选择一段连续的木桩，将它们涂成同一种颜色。但每次涂色都会覆盖之前的颜色。你的目标是找出涂完整个环形栅栏所需的最少涂色次数。 示例 输入： colors = "AAB" （环形） 输出：1 解释：由于是环形，你可以一次性将整个栅栏涂成颜色 'A'（覆盖掉原来的 'B'），所以只需要 1 次。 解题思路 环形处理 ：将环形问题转化为线性问题。方法是复制一份字符串，比如将 colors 复制为 colors + colors ，然后在这个长度为 2n 的字符串上求解线性版本的最小涂色次数，但最终只考虑长度为 n 的所有子串的最小值。 状态定义 ：设 dp[i][j] 表示涂完区间 [i, j] 所需的最少涂色次数。 状态转移 ： 如果 colors[i] == colors[j] ，那么涂区间 [i, j] 时，可以先涂 [i, j] 为同一种颜色，或者利用内部区间的结果： dp[i][j] = min(dp[i+1][j], dp[i][j-1]) 。 如果 colors[i] != colors[j] ，则需要将区间分割成两部分，枚举分割点 k ： dp[i][j] = min(dp[i][k] + dp[k+1][j]) ，其中 i ≤ k < j 。 初始化 ：单个木桩只需要涂色 1 次，即 dp[i][i] = 1 。 环形处理实现 ：对每个起始点 i （0 ≤ i < n），计算区间 [i, i+n-1] 的 dp 值，取最小值作为答案。 详细步骤 如果输入字符串长度为 1，直接返回 1。 复制字符串： s = colors + colors 。 初始化二维数组 dp ，大小为 2n × 2n ，初始值为 0。 遍历区间长度 len 从 1 到 n ： 对于每个起始点 i ，计算终点 j = i + len - 1 。 如果 len == 1 ， dp[i][j] = 1 。 否则： 如果 s[i] == s[j] ， dp[i][j] = min(dp[i+1][j], dp[i][j-1]) 。 否则， dp[i][j] = min(dp[i][k] + dp[k+1][j]) ，其中 k 从 i 到 j-1 。 遍历所有起始点 i （0 ≤ i < n），计算 dp[i][i+n-1] 的最小值，即为答案。 举例说明 输入： colors = "AAB" 复制后： s = "AABAAB" 计算线性区间 [0,2] （对应原环形）： dp[0][0]=1 , dp[1][1]=1 , dp[2][2]=1 dp[0][1] ：'A'='A'， dp[0][1] = min(dp[1][1], dp[0][0]) = min(1,1) = 1 dp[1][2] ：'A'≠'B'，枚举 k=1： dp[1][1]+dp[2][2]=2 dp[0][2] ：'A'≠'B'，枚举 k=0： dp[0][0]+dp[1][2]=1+2=3 ；k=1： dp[0][1]+dp[2][2]=1+1=2 ，取最小值 2。 但环形下，考虑区间 [2,4] （对应 "BAA"）可能更优，需计算所有起始点后取最小值。最终发现整个环形可一次涂色，答案为 1。 总结 本题通过复制字符串将环形转化为线性，利用区间动态规划枚举所有可能的分割点，逐步合并区间，得到最小涂色次数。关键点在于处理环形时的区间选取和状态转移时对端点颜色的判断。