区间动态规划例题：最小涂色次数问题（字符串染色问题，带颜色限制与相邻颜色不同的约束）
题目描述
给定一个长度为 \(n\) 的字符串 \(s\)，初始时每个字符都是无色（用特殊符号表示），现在要将整个字符串染成目标字符串 \(s\) \) 中的颜色（每个位置的目标颜色已知）。染色规则如下：
- 每次操作可以选择一个连续区间 \([l, r]\)，将这个区间内的所有位置染成同一种颜色。
- 如果某个位置之前已经染过色，新颜色会直接覆盖旧颜色。
- 相邻位置的颜色在染色完成后必须满足目标字符串的要求（即最终必须与目标一致），但在染色过程中颜色可以不同。
- 目标字符串中可能出现重复的颜色，但相邻位置颜色可能不同，要求最终染色结果与目标完全一致。
问：最少需要多少次染色操作，才能将整个无色字符串染成目标字符串 \(s\) 的颜色？
示例
输入：s = "abaca"
输出：3
解释：
- 将区间 [0, 4] 染成 'a'，此时字符串变为 "aaaaa"。
- 将区间 [1, 1] 染成 'b'，变为 "abaaa"。
- 将区间 [3, 3] 染成 'c'，变为 "abaca"。
解题思路（区间动态规划）
这个问题本质上是一个“分段覆盖”问题，我们可以用区间 DP 来求解。
定义状态：
- \(dp[l][r]\) 表示将区间 \([l, r]\) 染成目标颜色所需的最少操作次数。
最终答案是 \(dp[0][n-1]\)。
状态转移分析
关键观察
- 如果我们要染色区间 \([l, r]\)，第一次染色可以选择任意一种颜色，但为了最小化次数，我们通常让第一次染的颜色与目标字符串中某个位置的颜色相同，并且尽量延展到相邻相同颜色的位置。
- 如果 \(s[l] = s[r]\)，那么最优策略可能是先整个区间染成 \(s[l]\) 的颜色，再处理中间不同颜色的部分。
- 更一般地，如果 \(s[l] = s[k]\) 对某个 \(k\) 成立，我们可以考虑将区间分成子问题处理。
转移方程推导
情况 1：如果 \(s[l] = s[r]\)
- 我们可以第一次染色将整个区间 \([l, r]\) 染成 \(s[l]\) 的颜色，然后只需要处理中间那些与 \(s[l]\) 不同的部分。
- 但注意，如果 \(s[l] = s[r]\)，那么我们可以将区间拆分为：
\[ dp[l][r] = \min(dp[l+1][r], dp[l][r-1]) \]
为什么？
因为如果 \(s[l] = s[r]\)，那么我们可以将左端点颜色“借给”右端点，或者右端点颜色“借给”左端点，从而减少一次染色。
例如，如果最后一步染色左端点和右端点同时被染成目标颜色，那么它们可以共用一次染色操作。
情况 2：一般情况
- 我们枚举分割点 \(k\)，将区间分为 \([l, k]\) 和 \([k+1, r]\)，分别染色：
\[ dp[l][r] = \min_{k=l}^{r-1} (dp[l][k] + dp[k+1][r]) \]
- 但这样会忽略左右两端颜色相同的情况，所以我们需要结合情况 1 优化。
更优的转移：
标准解法（LeetCode 奇怪的打印机简化版）的思路是：
- 如果 \(s[l] = s[k]\) 对某个 \(k \in [l+1, r]\) 成立，那么我们可以考虑将区间 \([l, k]\) 和 \([k+1, r]\) 合并处理，因为 \(s[l]\) 和 \(s[k]\) 颜色相同，可以在同一次染色中完成。
- 具体转移方程：
\[ dp[l][r] = \min_{k=l}^{r-1} \left( dp[l][k] + dp[k+1][r] - (s[k] == s[r] \ ?\ 1 : 0) \right) \]
但这个形式有点复杂，下面给出更清晰的推导。
更简洁的推导
我们定义 \(dp[l][r]\) 为将区间 \([l, r]\) 染成目标颜色的最少操作数。
基础情况：
- 当 \(l = r\) 时，\(dp[l][r] = 1\)（一次染色即可）。
状态转移：
- 先考虑将区间分成左右两部分分别染色：
\[ dp[l][r] = \min_{k=l}^{r-1} (dp[l][k] + dp[k+1][r]) \]
- 如果 \(s[l] = s[r]\)，那么我们可以让第一次染色覆盖 \(l\) 和 \(r\) 为同一颜色，这样在染 \(l\) 和 \(r\) 时不需要额外操作。具体来说：
\[ dp[l][r] = \min(dp[l][r], dp[l][r-1]) \]
因为染区间 \([l, r]\) 时，可以先染成 \(s[r]\) 的颜色，而 \(s[l] = s[r]\)，所以左端点已经正确，只需处理 \([l, r-1]\) 的染色。
同理，也可以从 \(dp[l+1][r]\) 转移。
更准确的方程：
如果 \(s[l] = s[r]\)，那么
\[ dp[l][r] = dp[l][r-1] \]
为什么？
考虑区间 \([l, r]\)，如果 \(s[l] = s[r]\)，那么我们可以先将整个区间染成 \(s[r]\) 的颜色，此时 \(l\) 位置已经是正确的颜色，接下来只需要将 \([l, r-1]\) 染成目标颜色，而染 \([l, r-1]\) 时，第一次染色可以选择与 \(s[l]\) 相同的颜色，这样不会增加次数。
这个过程相当于：先染 \(r\) 颜色覆盖整个区间，然后递归处理 \([l, r-1]\)。
正确的状态转移方程（最终版）
我们从区间长度从小到大计算：
- 初始化：\(dp[i][i] = 1\)。
- 对于区间 \([l, r]\)，先假设最差情况是 \(dp[l][r] = dp[l][r-1] + 1\)，即先染好 \([l, r-1]\)，再单独染 \(r\)。
- 枚举分割点 \(k \in [l, r-1]\)，如果 \(s[k] = s[r]\)，那么我们可以将区间分成 \([l, k]\) 和 \([k+1, r-1]\) 两部分，并且染 \(k\) 和 \(r\) 可以在同一次操作中完成（因为它们颜色相同）。
此时转移为：
\[ dp[l][r] = \min(dp[l][r], dp[l][k] + dp[k+1][r-1]) \]
这里 \(dp[k+1][r-1]\) 表示区间 \([k+1, r-1]\) 的染色次数，而 \(k\) 和 \(r\) 颜色相同，可以在染 \([l, k]\) 时顺便染上 \(r\)。
实际上，更通用的方程是：
\[ dp[l][r] = \min_{k=l}^{r-1} \left( dp[l][k] + dp[k+1][r] - (s[k] == s[r] \ ?\ 1 : 0) \right) \]
这个方程的意思是：如果 \(s[k] = s[r]\)，那么 \(k\) 和 \(r\) 可以在一次染色中完成，所以总次数可以减少 1。
但这种方法复杂度较高，我们可以用更简单的思路：
如果 \(s[l] = s[r]\)，那么 \(dp[l][r] = dp[l][r-1]\)。
否则，枚举分割点 \(k\)：
\[ dp[l][r] = \min_{k=l}^{r-1} (dp[l][k] + dp[k+1][r]) \]
算法步骤（采用简化方程）
- 初始化 \(n = len(s)\)，\(dp[n][n]\) 为 0，\(dp[i][i] = 1\)。
- 按区间长度 \(len = 2\) 到 \(n\) 遍历：
- 对于每个区间 \([l, r]\)（\(r = l + len - 1\)）：
- 先令 \(dp[l][r] = dp[l][r-1] + 1\)（最差情况）。
- 如果 \(s[l] = s[r]\)，则 \(dp[l][r] = dp[l][r-1]\)。
- 枚举 \(k = l\) 到 \(r-1\)：
- 对于每个区间 \([l, r]\)（\(r = l + len - 1\)）：
\[ dp[l][r] = \min(dp[l][r], dp[l][k] + dp[k+1][r]) \]
- 返回 \(dp[0][n-1]\)。
示例推演
以 s = "abaca" 为例：
- 初始化：所有长度为 1 的区间 dp=1。
- 长度 2：
- [0,1]：s[0]!=s[1]，dp=min(dp[0][0]+dp[1][1]) = 2。
- [1,2]：s[1]!=s[2]，dp=2。
- [2,3]：s[2]!=s[3]，dp=2。
- [3,4]：s[3]!=s[4]，dp=2。
- 长度 3：
- [0,2]：s[0]!=s[2]，枚举 k：
k=0: dp[0][0]+dp[1][2]=1+2=3
k=1: dp[0][1]+dp[2][2]=2+1=3
取 min=3。 - 同理计算其他区间。
- [0,2]：s[0]!=s[2]，枚举 k：
- 最终 dp[0][4] 计算时会利用 s[0]=s[2]、s[2]=s[4] 等相同颜色减少次数，得到 3。
时间复杂度与空间复杂度
- 时间复杂度：\(O(n^3)\)，因为区间长度 \(O(n)\)，枚举区间 \(O(n^2)\)，枚举分割点 \(O(n)\)。
- 空间复杂度：\(O(n^2)\)。
总结
这道题是区间动态规划的经典问题，核心在于当区间两端颜色相同时，可以减少一次染色次数，从而优化转移方程。通过自底向上计算，可以高效求解最小染色次数。