合并相邻同色方块的最小成本问题（相邻染色限制版本） 题目描述： 给定一个由小写字母组成的字符串s，表示一排彩色方块。每次操作可以选择一个连续的同色方块区间，将其染成另一种颜色。但染色操作有一个限制：每次染色时，新颜色必须与相邻区域的颜色不同。我们的目标是用最少的染色次数，将所有方块染成同一种颜色。 解题过程： 问题分析： 这是一个区间染色问题，需要找到最少的染色次数 每次染色可以覆盖一个连续的同色区间 染色时新颜色必须与相邻区域颜色不同 最终目标是让整个字符串变成单一颜色 状态定义： 定义dp[ i][ j]表示将子串s[ i...j ]染成同一种颜色所需的最小染色次数。 状态转移方程： 考虑区间[ i, j ]的染色策略： 情况1：如果s[ i] == s[ j ] 我们可以先染整个区间为s[ i ]的颜色 或者先处理内部区间 dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) 情况2：如果s[ i] != s[ j ] 我们需要将区间分成两部分处理 dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j])，其中i ≤ k < j 但是这样还不够，我们需要考虑相邻染色限制。更准确的状态转移： 如果s[ i] == s[ j ]： dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) 否则： dp[ i][ j] = 1 + min(dp[ i+1][ j], dp[ i][ j-1 ]) 边界条件： 当i > j时，dp[ i][ j ] = 0（空区间） 当i == j时，dp[ i][ j ] = 0（单个字符已经是同色） 算法步骤： 步骤1：初始化n×n的dp数组，初始值为无穷大 步骤2：处理长度为1的区间，dp[ i][ i ] = 0 步骤3：按区间长度从小到大计算 步骤4：对于每个区间[ i, j ]，根据上述状态转移方程更新dp值 步骤5：最终答案在dp[ 0][ n-1 ]中 示例演示： 以字符串"aabaa"为例： 长度1：所有dp[ i][ i ] = 0 长度2："aa"：dp=0，"ab"：dp=1 逐步计算到整个字符串 最终最小染色次数为2 时间复杂度：O(n³)，空间复杂度：O(n²) 这个解法通过动态规划考虑了所有可能的染色顺序，确保了在相邻染色限制下找到最优解。