区间动态规划例题：最小涂色次数问题 题目描述 给定一个字符串s，每次操作可以选择一个连续区间并将该区间内的所有字符涂成同一种颜色（覆盖之前的颜色）。问至少需要多少次操作才能将整个字符串涂成目标颜色序列。 解题过程 问题分析 我们需要将空白画布（或任意初始状态）通过最少的涂色操作变成目标字符串 每次操作可以选择任意区间，将该区间全部涂成同一种颜色 关键观察：如果目标字符串中相邻字符相同，我们可以一次涂色完成多个相同字符 状态定义 定义dp[ i][ j]表示将区间[ i,j ]涂成目标颜色所需的最小操作次数。 基础情况 当区间长度为1时（i = j），只需要1次操作：dp[ i][ i ] = 1 状态转移方程 考虑区间[ 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 ] 我们需要找到分割点k，将区间分为[ i,k]和[ k+1,j ]： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j])，其中i ≤ k < j 解释：将区间分成两部分分别涂色，然后合并操作次数 具体计算步骤 以字符串"abaca"为例： 步骤1：初始化对角线 dp[ 0][ 0 ] = 1 ("a") dp[ 1][ 1 ] = 1 ("b") dp[ 2][ 2 ] = 1 ("a") dp[ 3][ 3 ] = 1 ("c") dp[ 4][ 4 ] = 1 ("a") 步骤2：计算长度为2的区间 [ 0,1]："ab"，s[ 0]≠s[ 1 ] dp[ 0][ 1] = min(dp[ 0][ 0]+dp[ 1][ 1 ]) = 1+1 = 2 [ 1,2]："ba"，s[ 1]≠s[ 2 ] dp[ 1][ 2] = min(dp[ 1][ 1]+dp[ 2][ 2 ]) = 1+1 = 2 [ 2,3]："ac"，s[ 2]≠s[ 3 ] dp[ 2][ 3] = min(dp[ 2][ 2]+dp[ 3][ 3 ]) = 1+1 = 2 [ 3,4]："ca"，s[ 3]≠s[ 4 ] dp[ 3][ 4] = min(dp[ 3][ 3]+dp[ 4][ 4 ]) = 1+1 = 2 步骤3：计算长度为3的区间 [ 0,2]："aba"，s[ 0]=s[ 2 ]='a' dp[ 0][ 2] = min(dp[ 1][ 2], dp[ 0][ 1 ]) = min(2,2) = 2 解释：可以先涂整个区间为'a'，然后修改中间字符 [ 1,3]："bac"，s[ 1]≠s[ 3 ] 尝试所有分割点： k=1: dp[ 1][ 1]+dp[ 2][ 3 ] = 1+2 = 3 k=2: dp[ 1][ 2]+dp[ 3][ 3 ] = 2+1 = 3 dp[ 1][ 3 ] = min(3,3) = 3 [ 2,4]："aca"，s[ 2]=s[ 4 ]='a' dp[ 2][ 4] = min(dp[ 3][ 4], dp[ 2][ 3 ]) = min(2,2) = 2 步骤4：计算长度为4的区间 [ 0,3]："abac"，s[ 0]≠s[ 3 ] 尝试分割点： k=0: dp[ 0][ 0]+dp[ 1][ 3 ] = 1+3 = 4 k=1: dp[ 0][ 1]+dp[ 2][ 3 ] = 2+2 = 4 k=2: dp[ 0][ 2]+dp[ 3][ 3 ] = 2+1 = 3 dp[ 0][ 3 ] = 3 [ 1,4]："baca"，s[ 1]≠s[ 4 ] 尝试分割点： k=1: dp[ 1][ 1]+dp[ 2][ 4 ] = 1+2 = 3 k=2: dp[ 1][ 2]+dp[ 3][ 4 ] = 2+2 = 4 k=3: dp[ 1][ 3]+dp[ 4][ 4 ] = 3+1 = 4 dp[ 1][ 4 ] = 3 步骤5：计算整个区间[ 0,4] "abaca"，s[ 0]=s[ 2]=s[ 4]='a'，但s[ 0]≠s[ 4]？实际上s[ 0]='a'，s[ 4]='a'，所以s[ 0]=s[ 4 ] 应用情况1：dp[ 0][ 4] = min(dp[ 1][ 4], dp[ 0][ 3 ]) = min(3,3) = 3 最终结果 ：最少需要3次操作 算法验证 一种可行的3次操作方案： 涂整个区间为'a' → "aaaaa" 涂区间[ 1,1 ]为'b' → "abaaa" 涂区间[ 3,3 ]为'c' → "abaca" 这个算法的时间复杂度是O(n³)，空间复杂度是O(n²)。