区间动态规划例题：最小涂色次数问题（相邻染色限制版本） 题目描述 给定一个长度为n的字符串s，表示一排需要涂色的格子。每个格子可以涂成红色(R)、绿色(G)或蓝色(B)中的一种颜色。但是存在相邻染色限制：相邻的两个格子不能涂成相同的颜色。 每次操作，你可以选择一段连续的区间并将该区间内所有格子涂成同一种颜色。问最少需要多少次操作，才能完成所有格子的涂色，且满足相邻染色限制。 解题思路 这是一个典型的区间动态规划问题。我们需要找到最少的连续区间涂色次数来满足相邻颜色限制。 关键观察 如果字符串长度为1，只需要1次操作 如果相邻两个字符相同，根据限制条件这是不允许的（但题目输入可能包含这种情况，我们需要处理） 区间DP的思路：将大区间划分为两个小区间，考虑合并时的代价 DP状态定义 定义dp[ i][ j]表示将区间[ i,j ]正确涂色所需的最小操作次数。 状态转移方程 基础情况：当i = j时，dp[ i][ j ] = 1（单个格子需要一次操作） 当s[ i] == s[ j ]时： 如果可以在同一次操作中涂色区间[ i,j ]，且满足相邻限制 具体分析：dp[ i][ j] = min(dp[ i][ j], dp[ i+1][ j-1 ] + 1) 但需要谨慎处理边界条件 一般情况：将区间[ i,j ]在位置k处分割 dp[ i][ j] = min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j ]) 但需要注意：如果s[ k] == s[ k+1 ]，这种分割可能不合法 详细推导过程 让我们通过一个例子来理解：字符串"RGB" 步骤1：处理长度为1的区间 dp[ 0][ 0 ] = 1（涂色"R"） dp[ 1][ 1 ] = 1（涂色"G"） dp[ 2][ 2 ] = 1（涂色"B"） 步骤2：处理长度为2的区间 区间[ 0,1 ]："RG" 检查相邻限制：R≠G，满足条件 可以一次涂色完成吗？不行，因为需要两种颜色 最小操作次数：dp[ 0][ 1 ] = 2 区间[ 1,2 ]："GB" 同样需要2次操作：dp[ 1][ 2 ] = 2 步骤3：处理长度为3的区间[ 0,2]："RGB" 考虑所有可能的分割点： 在k=0处分割：[ 0,0]和[ 1,2 ] dp[ 0][ 0] + dp[ 1][ 2 ] = 1 + 2 = 3 在k=1处分割：[ 0,1]和[ 2,2 ] dp[ 0][ 1] + dp[ 2][ 2 ] = 2 + 1 = 3 但我们可以找到更优解：实际上"RGB"可以用2次操作完成： 第一次：涂色区间[ 0,2 ]为某种颜色（比如R） 第二次：分别涂色位置1为G，位置2为B 但这样会违反相邻限制，因为位置0和1都是R 实际上，"RGB"需要3次操作，每个位置单独涂色。 修正的状态转移方程 经过更深入分析，我们需要更精细的状态设计： 定义dp[ i][ j][ c]表示将区间[ i,j ]涂色，且区间左端颜色为c时的最小操作次数。 但这样状态太多，我们可以简化： 更优的DP定义 dp[ i][ j]表示将区间[ i,j ]按照要求涂色的最小操作次数。 状态转移： 如果s[ i] == s[ j ]且i≠j： 我们可以考虑将整个区间先涂成s[ i ]的颜色，然后处理内部 dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) 但需要确保相邻颜色不冲突 一般情况： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j]) 对于所有i ≤ k < j 但如果s[ k] == s[ k+1 ]，需要减1，因为可以合并操作 最终算法实现 经过仔细分析，正确的状态转移方程为： 对于区间[ i,j ]： 如果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] - (s[ k] == s[ k+1] ? 1 : 0)) 对于所有i ≤ k < j 边界条件 ：dp[ i][ i ] = 1 举例验证 字符串"RGBR"： 按照上述算法计算可得最小操作次数为3 具体操作序列： 涂色整个区间为R 涂色位置1为G 涂色位置2为B 但这样位置3和位置0都是R，相邻冲突 实际正确操作：每个位置单独涂色，需要4次操作 算法复杂度 时间复杂度：O(n³)，需要三层循环 空间复杂度：O(n²)，DP表的大小 这个问题的关键在于正确处理相邻颜色限制对区间合并的影响，以及找到最优的分割策略。