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

题目描述
给定一个长度为 n 的字符串 s，表示一排需要涂色的格子。每次操作可以选择一个区间 [l, r] 并涂上同一种颜色，但要求该区间内所有格子当前颜色相同（初始时所有格子无色，可视为空白）。求将整个字符串涂成目标颜色所需的最少操作次数。

示例
输入：s = "aabbaa"
输出：4
解释：一种可行的涂色顺序为：

1. 涂整个区间为 'a'（但此时中间 "bb" 不符合要求，因此不能一次性涂整个字符串）
   实际最小操作序列可能为：

• 涂 [0,5] 为 'a'（无效，因为 "bb" 区域初始无色但要求一次性涂同色区间）
  正确思路：先涂底层相同颜色区间，再覆盖。具体步骤：

1. 涂 [0,1] 为 'a'
2. 涂 [2,3] 为 'b'
3. 涂 [4,5] 为 'a'
4. 涂 [1,4] 为 'a'（覆盖 [1,1] 和 [4,4] 的 'a'，并覆盖 [2,3] 的 'b'）
   但此策略非最优。实际动态规划解法会得到更优解。

解题过程

1. 问题分析

• 每次操作涂一个区间，且区间内当前颜色必须相同（初始无色视为可任意涂，但目标颜色固定）。
• 关键观察：若 s[i] == s[j]，则涂 [i,j] 时可能可减少操作次数（例如先涂两端同色，再处理中间）。
• 本题是区间DP经典问题，类似“奇怪的打印机”，但强调相邻染色限制。

2. 状态定义
定义 dp[i][j] 表示将区间 [i, j] 涂成目标颜色所需的最少操作次数。

3. 状态转移方程

• 基础情况：当 i == j，只需涂一次，dp[i][j] = 1。
• 一般情况（i < j）：
  • 如果 s[i] == s[j]：
    涂 [i, j] 时，可先涂 [i, j] 为 s[i]（颜色同两端），然后分别处理 [i+1, j-1]。但注意：涂 [i, j] 后，[i+1, j-1] 可能已被覆盖，因此需考虑子区间。
    实际转移：dp[i][j] = min(dp[i+1][j], dp[i][j-1])。
    解释：因为 s[i] == s[j]，涂 [i, j] 时可视为一次操作覆盖整个区间，然后只需处理一侧子区间。
  • 如果 s[i] != s[j]：
    需分割区间，枚举分割点 k（i ≤ k < j）：
    dp[i][j] = min(dp[i][k] + dp[k+1][j])。
    解释：将区间分成两部分分别涂色，操作次数为两部分之和。

4. 初始化与计算顺序

• 初始化：dp[i][i] = 1。
• 计算顺序：按区间长度 len 从小到大（len = 2 到 n），计算所有 [i, j]（j = i+len-1）。

5. 示例推导
以 s = "aabbaa" 为例：

• 初始化：所有 dp[i][i] = 1。
• 长度2：
  • [0,1]: s[0]=='a'==s[1]=='a' → dp[0][1] = min(dp[1][1], dp[0][0]) = min(1,1) = 1
  • [1,2]: 'a' != 'b' → dp[1][2] = min(dp[1][1]+dp[2][2]) = 2
  • 类似计算所有长度2区间。
• 长度3及以上：
  • 例如 [0,2]: s[0]=='a' != s[2]=='b' → 枚举 k=0,1：
    • 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
  • 最终 dp[0][5] 为答案。

6. 算法实现

def minPaint(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n + 1):
        for i in range(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] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
    return dp[0][n-1]

7. 复杂度分析

• 时间复杂度：O(n³)（三重循环）。
• 空间复杂度：O(n²)（DP表）。

总结
本题通过区间DP建模，关键点在于处理两端字符相同时可减少操作次数。通过自底向上计算子区间最优解，最终得到整个字符串的最小涂色次数。