区间动态规划例题：最小涂色次数问题（字符串染色问题） 题目描述 给定一个字符串s，你需要将字符串染成目标颜色。每次染色操作可以选择一个区间，将这个区间内的所有字符染成同一种颜色。问最少需要多少次染色操作才能将整个字符串染成目标颜色。 注意：初始时字符串是空白的（可以认为是无色），或者你可以假设初始字符串与目标完全不同。目标颜色由字符串s给出，s[ i ]表示位置i的目标颜色。 示例： 输入：s = "aabaa" 输出：2 解释：第一次染色整个字符串为'a'，第二次染色中间三个字符为'b'。 解题思路 这个问题可以用区间动态规划解决。我们定义dp[ i][ j]表示将区间[ i,j ]染成目标颜色所需的最小染色次数。 基本思路推导 基础情况 ：当区间长度为1时，只需要1次染色操作。 状态转移分析 ： 如果s[ i] == s[ j]，那么我们可以先染整个区间为s[ i ]的颜色，这样可能比分别染色更优 对于任意区间[ i,j]，我们可以考虑将其分成两个子区间[ i,k]和[ k+1,j ] 关键观察 ：如果区间两端的颜色相同，我们可以优化染色策略。 详细解题步骤 步骤1：定义状态 定义dp[ i][ j]为将区间[ i,j ]染成目标颜色所需的最小染色次数。 步骤2：初始化基础情况 对于长度为1的区间： dp[ i][ i ] = 1（每个单独字符都需要一次染色） 步骤3：状态转移方程 我们按区间长度从小到大进行计算： 如果s[ i] == s[ j ]： dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) 解释：如果两端颜色相同，我们可以利用其中一端的染色来覆盖另一端 对于所有k (i ≤ k < j)： dp[ i][ j] = min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j ]) 解释：将区间分成两部分分别染色 步骤4：算法实现 以s = "aabaa"为例，演示计算过程： 初始化对角线： dp[ 0][ 0]=1, dp[ 1][ 1]=1, dp[ 2][ 2]=1, dp[ 3][ 3]=1, dp[ 4][ 4 ]=1 计算长度为2的区间： [ 0,1]: s[ 0]=='a'==s[ 1]=='a' ⇒ dp[ 0][ 1]=min(dp[ 1][ 1], dp[ 0][ 0 ])=1 [ 1,2]: 'a'≠'b' ⇒ 考虑分割点k=1 ⇒ min(dp[ 1][ 1]+dp[ 2][ 2 ])=2 [ 2,3]: 'b'≠'a' ⇒ min(dp[ 2][ 2]+dp[ 3][ 3 ])=2 [ 3,4]: 'a'=='a' ⇒ min(dp[ 4][ 4], dp[ 3][ 3 ])=1 计算长度为3的区间： 分割点k=0: dp[ 0][ 0]+dp[ 1][ 2 ]=1+2=3 分割点k=1: dp[ 0][ 1]+dp[ 2][ 2 ]=1+1=2 ⇒ dp[ 0][ 2 ]=2 继续计算直到整个区间[ 0,4 ] 步骤5：最终结果 dp[ 0][ 4 ]就是整个字符串的最小染色次数。 复杂度分析 时间复杂度：O(n³)，需要三层循环 空间复杂度：O(n²)，用于存储dp数组 优化思路 对于s[ i] == s[ j ]的情况，可以进一步优化： dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1], dp[ i+1][ j-1 ] + 1) 当两端颜色相同时，我们还可以考虑先染整个区间为s[ i ]的颜色。