区间动态规划例题：最小涂色次数问题（相邻染色限制版本）

题目描述
给定一个长度为n的字符串s，表示一排需要涂色的格子。每个格子可以涂成红色(R)、绿色(G)或蓝色(B)中的一种颜色。但是存在限制：相邻的两个格子不能涂成相同的颜色。

每次操作可以选择一个连续的区间，并将该区间内的所有格子涂成同一种颜色。问最少需要多少次操作，才能完成对整个字符串的涂色要求。

解题思路分析
这个问题看似简单的涂色问题，但实际上需要区间动态规划来高效解决。关键难点在于如何将整个涂色过程分解为子问题。

核心观察

1. 如果字符串长度为1，显然只需要1次操作
2. 如果第一个格子和最后一个格子颜色相同，我们可以考虑先涂整个区间，然后再处理内部
3. 操作的最优策略通常是从外向内逐步涂色

动态规划状态定义
定义dp[i][j]表示完成区间[i,j]的涂色所需的最小操作次数。

状态转移方程推导

情况1：基础情况
当i = j时，即单个格子：dp[i][j] = 1

情况2：首尾颜色相同
如果s[i] == s[j]：

• 我们可以先涂整个区间为s[i]的颜色（1次操作）
• 然后处理内部区间[i+1,j-1]
• 但是注意：由于相邻格子颜色限制，内部处理可能更复杂

更精确的转移：
dp[i][j] = min(dp[i+1][j], dp[i][j-1])

为什么这样转移？
因为当首尾颜色相同时，我们可以在涂其中一个端点的时候"顺便"涂另一个端点。比如：

• 先涂[i,j-1]区间，然后调整右端点
• 或者先涂[i+1,j]区间，然后调整左端点

情况3：首尾颜色不同
如果s[i] ≠ s[j]：
我们需要在区间内找一个分割点k，将区间分为[i,k]和[k+1,j]
dp[i][j] = min(dp[i][k] + dp[k+1][j])，其中i ≤ k < j

详细解题过程

步骤1：初始化
对于所有i从0到n-1：dp[i][i] = 1

步骤2：按区间长度递增计算

for length in range(2, n+1):      # 区间长度从2到n
    for i in range(0, n-length+1):  # 区间起始点
        j = i + length - 1         # 区间结束点
        
        if s[i] == s[j]:
            # 首尾颜色相同的情况
            dp[i][j] = min(dp[i+1][j], dp[i][j-1])
        else:
            # 首尾颜色不同的情况
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

步骤3：示例分析
以字符串"RGB"为例：

• dp[0][0]=1, dp[1][1]=1, dp[2][2]=1
• 区间[0,1]："RG"，颜色不同
  dp[0][1] = min(dp[0][0]+dp[1][1]) = 1+1 = 2
• 区间[1,2]："GB"，颜色不同
  dp[1][2] = min(dp[1][1]+dp[2][2]) = 1+1 = 2
• 区间[0,2]："RGB"
  s[0]='R' ≠ s[2]='B'，颜色不同
  分割点k=0：dp[0][0]+dp[1][2] = 1+2 = 3
  分割点k=1：dp[0][1]+dp[2][2] = 2+1 = 3
  dp[0][2] = min(3, 3) = 3

步骤4：优化理解
实际上，当首尾颜色相同时，我们有一个重要的优化：
如果s[i] == s[j]，那么dp[i][j] = dp[i+1][j]（或dp[i][j-1]）

这是因为我们可以用一次操作涂整个区间为s[i]的颜色，然后内部可能需要更少的操作。但通过数学证明，直接取两边子区间的最小值就是最优解。

复杂度分析

• 时间复杂度：O(n³)，需要三重循环
• 空间复杂度：O(n²)，用于存储dp数组

最终答案
整个字符串的最小涂色次数就是dp[0][n-1]

这个问题的关键在于理解：当首尾颜色相同时，我们可以通过更少的操作完成涂色，因为可以"一次性"处理外层的相同颜色。