最小涂色次数问题（相邻染色限制版本） 题目描述： 给定一个长度为n的字符串s，表示一排需要涂色的格子，每个字符表示该格子需要的颜色。你有一个涂色刷，每次可以选择一个连续的区间涂上同一种颜色。但有一个限制：相邻的两个格子如果被涂成相同颜色，那么它们必须在同一次涂色操作中完成。问最少需要多少次涂色操作才能完成所有格子的涂色。 解题过程： 问题分析： 我们需要将整个字符串涂成目标颜色 每次涂色可以选择任意连续区间，涂成同一种颜色 关键限制：如果相邻两个格子颜色相同，它们必须在同一次操作中完成 这意味着相同颜色的连续段必须一次性涂完 状态定义： 定义dp[ i][ j]表示将区间[ i,j ]涂成目标颜色所需的最小涂色次数。 状态转移： 情况1：如果s[ i] == s[ j ] 我们可以先涂整个区间为s[ i ]的颜色，然后处理内部 但这样可能不是最优，因为内部可能有更高效的涂法 情况2：一般情况 将区间[ i,j]分成两部分：[ i,k]和[ k+1,j ] dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j])，其中i ≤ k < j 但是我们需要考虑相邻染色限制的影响。 详细的状态转移方程： 基础情况：当i == j时，dp[ i][ j ] = 1（单个格子需要一次涂色） 当i < j时： 如果s[ i] == s[ j ]： 我们可以考虑两种策略： 策略1：先涂整个区间为s[ i ]的颜色（1次），然后处理内部不同颜色的部分 策略2：将区间分割，分别处理 实际上，当s[ i] == s[ j ]时，我们可以减少一次操作： dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) 因为如果首尾颜色相同，我们可以扩展涂色范围 如果s[ i] != s[ j ]： 我们需要分割区间： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j])，其中i ≤ k < j 算法步骤： 步骤1：初始化dp数组 对于所有i，dp[ i][ i ] = 1 步骤2：按区间长度从小到大计算 对于长度L从2到n： 对于每个起始位置i，计算j = i + L - 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])，其中i ≤ k < j 示例说明： 以字符串"a b a"为例： dp[ 0][ 0] = 1, dp[ 1][ 1] = 1, dp[ 2][ 2 ] = 1 计算[ 0,1]：'a' != 'b'，dp[ 0][ 1] = dp[ 0][ 0] + dp[ 1][ 1 ] = 2 计算[ 1,2]：'b' != 'a'，dp[ 1][ 2 ] = 2 计算[ 0,2]：'a' == 'a'，dp[ 0][ 2] = min(dp[ 1][ 2], dp[ 0][ 1 ]) = min(2,2) = 2 时间复杂度：O(n³)，空间复杂度：O(n²) 关键理解： 相邻染色限制体现在状态转移中：当首尾颜色相同时，我们可以减少操作次数 这是因为我们可以利用已有的涂色范围进行扩展，而不需要额外的操作 这个问题实际上是"奇怪的打印机"问题的简化版本，但约束条件不同