合并相邻同色字符的最小操作次数问题（每次操作可以合并两个相邻且颜色相同的字符，合并后生成一个新字符，且新字符颜色可能变化，并产生一定操作次数消耗，求将整个字符串合并为一个字符的最小操作次数）
问题描述
我们有一个长度为 \(n\) 的字符串 \(s\)，其中每个字符有一个颜色（可以用整数表示）。
每次操作可以选择两个相邻且颜色相同的字符，将它们合并成一个新的字符。
新字符的颜色由一个给定的规则决定（例如通过查表，或者通过某种计算得到），并且每次操作需要消耗 1 次操作次数。
目标是：通过一系列合并操作，最终将整个字符串合并为 一个字符，并且要求 总操作次数最小。
注意：
- 合并只能发生在相邻且颜色相同的字符之间。
- 合并后，新字符的颜色可能和原颜色不同。
- 如果相邻字符颜色不同，则不能合并。
- 最终必须合并到只剩一个字符，如果无法合并到只剩一个字符，则返回 -1 或表示不可能。
通常，题目会给出一个 颜色转移表 \(trans[a][b]\)，表示当两个颜色为 \(a\) 的字符合并时，生成的新颜色为 \(trans[a][b]\)（有时与 \(b\) 无关，只与 \(a\) 有关，即 \(trans[a]\)）。
示例
假设颜色种类只有 0, 1, 2。
转移规则：
- 两个颜色 0 合并 → 新颜色 1
- 两个颜色 1 合并 → 新颜色 2
- 两个颜色 2 合并 → 新颜色 0
字符串 \(s = [0, 1, 0, 1, 2]\)
我们想知道能否合并为一个字符，以及最少操作次数。
思路分析
这是一个典型的 区间动态规划 问题，因为合并操作会不断将相邻区间合并成一种颜色，最终整个区间变成一种颜色。
定义状态：
\(dp[i][j][c]\) = 能否将子串 \(s[i..j]\) 合并成颜色为 \(c\) 的单个字符，如果可以，最小操作次数是多少；如果不能，则为无穷大（或标记不可行）。
最终答案：
对所有可能的最终颜色 \(c\)，取 \(dp[0][n-1][c]\) 的最小值。
状态转移推导
对于区间 \([i, j]\)，我们想把它合并成颜色 \(c\)。
如何合并？
最后一步合并时，区间 \([i, j]\) 由两个子区间 \([i, k]\) 和 \([k+1, j]\) 分别合并成颜色 \(c_1\) 和 \(c_2\)，并且这两个颜色相同（因为只有相邻且颜色相同的字符才能合并），且合并后变成颜色 \(c\)。
所以：
- 先让 \([i, k]\) 合并成颜色 \(c_1\)（操作次数 \(dp[i][k][c_1]\)）
- 再让 \([k+1, j]\) 合并成颜色 \(c_2\)（操作次数 \(dp[k+1][j][c_2]\)）
- 要求 \(c_1 = c_2\)（否则无法合并这两个区间）
- 根据规则，两个颜色 \(c_1\) 合并成新颜色 \(trans[c_1]\)，这里必须等于 \(c\)
- 总操作次数 = \(dp[i][k][c_1] + dp[k+1][j][c_1] + 1\)（最后一步合并操作）
所以转移方程：
\[dp[i][j][c] = \min_{i \le k < j, \; c_1 \in colors} \left\{ dp[i][k][c_1] + dp[k+1][j][c_1] + 1 \right\} \]
其中要求 \(trans[c_1] = c\)（即合并后必须得到目标颜色 \(c\)）。
初始条件
对于区间长度为 1 的情况：
\(dp[i][i][s[i]] = 0\)（已经是颜色 \(s[i]\)，不需要合并）
\(dp[i][i][c] = \infty\)（对于其他颜色 \(c \neq s[i]\) 不可能）
计算顺序
区间 DP 通常按区间长度从小到大计算：
- 先算所有长度为 1 的区间
- 再算长度为 2 的区间：需要合并两个字符，它们颜色必须相同，才能合并成 \(trans[color]\)，操作次数为 1
- 再算长度为 3, 4, ..., n 的区间
实现细节
设颜色种类数为 \(m\)，字符串长度为 \(n\)。
状态数组大小：\(dp[n][n][m]\)
时间复杂度：
- 外层循环长度 \(len = 2\) 到 \(n\)
- 内层循环起点 \(i\)
- 内层循环分割点 \(k\)
- 枚举颜色 \(c_1\)（用于左右区间）
- 然后得到新颜色 \(c = trans[c_1]\)
总复杂度 \(O(n^3 \cdot m)\)
举例详细推演
假设颜色集合 {0,1,2}，转移规则如上。
字符串 s = [0,1,0,1,2]，长度 5。
初始化：
dp[0][0][0] = 0, 其他 dp[0][0][c]=∞
dp[1][1][1] = 0
dp[2][2][0] = 0
dp[3][3][1] = 0
dp[4][4][2] = 0
长度 2：
[0,1]: 颜色 0 和 1 不同，不能合并 → 对所有 c 都是 ∞
[1,2]: 1 和 0 不同 → ∞
[2,3]: 0 和 1 不同 → ∞
[3,4]: 1 和 2 不同 → ∞
长度 3：
以 [0,2] = [0,1,0] 为例：
可能的分割点 k=0,1
尝试 k=0: [0,0] 颜色 0, [1,2] 需要合并成颜色 0 才能和左边合并。检查 [1,2] 能否变成颜色 0。
[1,2] 长度 2，颜色分别是 1 和 0，不同，不能合并成任何颜色 → 不可能
k=1: [0,1] 需要变成颜色 c1, [2,2] 颜色 0。要合并，c1 必须等于 0，但 [0,1] 长度 2，不可能合并成颜色 0（因为 0 和 1 不同）。所以不可能。
因此 [0,2] 不能合并成一个字符。
我们跳过详细推演（篇幅有限），最终我们要检查整个 [0,4] 能否合并成某种颜色并求最小次数。
在实际问题中，可能有些状态可达，有些不可达。最终取 min(dp[0][n-1][c]) 若为 ∞ 则返回 -1。
优化思考
有时可以简化：
因为最后合并的两个区间颜色必须相同，所以我们可以定义另一个状态：
\(f[i][j]\) = 将 [i..j] 合并成一个字符的最少操作次数（不指定颜色），同时记录合并后的颜色。
但这样需要同时追踪颜色，否则不知道下一步合并规则。
常用方法还是三维 dp[i][j][c]。
小结
这个问题的核心是：
- 识别为区间 DP，因为合并相邻区间直到整个区间变成一个字符。
- 状态要包含最终颜色，因为合并规则依赖于颜色。
- 转移时，枚举最后一步合并的分割点，要求左右区间合并成相同颜色，再根据规则得到新区间颜色。
通过这个模板，你可以解决类似“合并相邻同色字符，颜色变化，求最小操作次数”的问题。