合并相邻同色字符的最小操作次数问题（每次合并两个相邻且颜色相同的字符，合并产生新字符，新字符颜色可不同，有不同合并成本）

题目描述

你有一个字符串 s，其中每个字符 s[i] 有一种颜色（可以用整数表示，比如 1 到 k）。
你每次可以选择 两个相邻且颜色相同的字符 进行合并，合并后会得到一个 新字符，新字符的颜色可以不同于原来的颜色（但颜色种类仍在 1 到 k 之间）。
不同颜色之间的合并，会有一个特定的成本（给定一个 cost[a][b] 表示将两个颜色为 a 的字符合并成一个颜色为 b 的新字符的成本）。
你的目标是通过若干次合并，最终将整个字符串合并成 一个字符，求 最小的总成本。
如果无法合并成一个字符，返回 -1。

示例（假设颜色数量 k=3）：
字符串颜色序列：[1, 2, 1, 2, 1]
成本矩阵 cost[a][b] 是已知的，比如 cost[1][2] = 3 表示将两个颜色 1 的字符合并成颜色 2 的成本是 3。
问：最小总成本是多少？

解题思路

这是一个区间动态规划问题，但比简单的合并石子复杂，因为合并后新颜色不确定，而且只有相邻且颜色相同的字符才能合并。

关键点理解

1. 合并的条件是两个字符颜色相同，才能合并成一个新颜色的字符。
2. 合并后产生的新颜色可以是任意颜色（1 到 k）。
3. 最终的目标是让整个区间 [0, n-1] 合并成一个字符。
4. 我们需要在 DP 中记录区间合并成某种颜色的最小成本。

状态定义

定义：

• n 为字符串长度，下标从 0 到 n-1。
• color[i] 是位置 i 的初始颜色（1 到 k）。
• cost[a][b] 是合并两个颜色 a 的字符，得到颜色 b 的新字符的成本。

设 dp[l][r][c] 表示将子串 [l, r] 合并成 一个颜色为 c 的字符 的最小成本。
如果无法将 [l, r] 合并成一个颜色 c 的字符，则值为无穷大。

状态转移

基本思路：
对于一个区间 [l, r]，要合并成一个颜色 c 的字符，我们需要考虑最后一次合并发生在哪里：

• 如果 l == r，那么这个区间已经是一个字符，颜色固定为初始颜色 color[l]。
  所以只有 dp[l][r][color[l]] = 0，其他颜色都是不可能的（无穷大）。

• 如果 l < r，我们可以将区间拆分成 [l, m] 和 [m+1, r] 吗？
  不行，因为合并规则要求两个相邻且颜色相同的字符才能合并，而这里拆分后左右两段合并出来的颜色可能不同，无法直接合并。
  所以需要换一种方式：我们假设最终要合并出颜色 c，那么最后一次合并一定是将两个颜色相同的字符合并成一个颜色 c 的新字符。
  这两个相同颜色的字符来自哪里？
  它们一定是整个区间 [l, r] 的某个分割点，使得左半段合并成一个颜色 a，右半段合并成一个颜色 a，然后合并这两个颜色 a 的字符，得到颜色 c，成本为 cost[a][c]。

  所以状态转移为：

  dp[l][r][c] = min over a in 1..k, m in [l, r-1] {
      dp[l][m][a] + dp[m+1][r][a] + cost[a][c]
  }
  

  这里 m 是将区间分成两段，两段分别合并成一个颜色 a 的字符，然后合并这两个颜色 a 的字符得到颜色 c。

初始化

dp[l][l][color[l]] = 0，其他 dp[l][l][c] = INF。

计算顺序

因为 dp[l][r][c] 依赖于更小的区间长度，所以我们按区间长度从小到大计算。
长度 len 从 2 到 n，对每个区间 [l, r]（r = l+len-1），枚举分割点 m，枚举颜色 a 和 c。

最终答案

我们要求的是整个区间 [0, n-1] 合并成一个字符的最小成本，不关心最终颜色。
所以答案是：

ans = min over c in 1..k { dp[0][n-1][c] }

如果所有都是 INF，则返回 -1。

复杂度分析

状态数：O(n^2 * k)
转移：O(n * k^2)（对每个区间枚举分割点 m 和颜色 a, c，但注意 m 是 O(n)，颜色 a 和 c 是 O(k^2)）
总复杂度 O(n^3 * k^2)，在 n 较小（比如 ≤ 50）且 k 较小（比如 ≤ 5）时可以接受。

示例演算

假设颜色 k=3，初始序列颜色：[1, 2, 1]（n=3）
cost 矩阵（假设对称且简单）：

cost[a][b] = 0 如果 a==b
cost[a][b] = 1 如果 a!=b

目标：合并成单个字符的最小成本。

1. 初始化：
   dp[0][0][1] = 0
   dp[1][1][2] = 0
   dp[2][2][1] = 0

2. 计算长度 2：

   • 区间 [0,1]：颜色 1 和 2 不同，不能直接合并成一个字符，需要尝试分割？
     这里 m=0, 左dp[0][0][a] 和右 dp[1][1][a] 要颜色相同才能合并。
     如果 a=1，左是 0，右是 INF（因为右段颜色 2 无法变成 1），不行。
     如果 a=2，左是 INF，右是 0，不行。
     所以 dp[0][1][c] 对任意 c 都是 INF（无法合并）。
   • 区间 [1,2]：颜色 2 和 1 不同，同理无法合并。

3. 计算长度 3 [0,2]：
   枚举 m=0 和 m=1。
   先看 m=0：

   • 左 [0,0] 颜色 1，右 [1,2] 需要合并成颜色 1 才能与左合并。
     右 [1,2] 能否合并成颜色 1？
     右段 [1,2] 初始颜色 2 和 1，不同，无法直接合并成一个字符，所以 dp[1][2][1]=INF。
     所以 m=0 不行。
     再看 m=1：
   • 左 [0,1] 需要合并成颜色 a，但 dp[0][1][a] 都是 INF，所以不行。

   因此最终 dp[0][2][c] 都是 INF，无法合并成一个字符，答案 -1。

这个例子说明如果相邻字符颜色都不相同，则一次合并都无法进行，返回 -1。

扩展与思考

• 如果题目允许一次合并多个相邻同色字符（比如一次合并连续三个颜色相同的字符），状态转移会不同，但核心还是区间 DP。
• 如果 cost 矩阵不对称，即合并成不同颜色的成本不同，则转移时需注意方向。
• 实际编程时，可以用三维数组，但注意 INF 用一个大数表示不可行。

这个题目结合了区间 DP 与状态（颜色）枚举，是一个典型的“区间合并颜色变化”问题。