“合并相邻同色字符的最小操作次数问题（每次操作可以合并两个相邻且颜色相同的字符，合并后生成一个新字符，且新字符颜色可能变化，并产生一定操作次数消耗，求将整个字符串合并为一个字符的最小操作次数）”

题目描述

给定一个由小写字母组成的字符串 s，长度为 n。每个字符代表一种颜色。你可以重复进行以下操作：
选择两个相邻且颜色相同的字符，将它们合并为一个新字符。新字符的颜色由规则决定（例如，可能是固定的另一种颜色，或根据某种映射表确定），并且每次操作会消耗 1 次操作计数。
目标是通过一系列合并操作，最终将整个字符串合并为一个字符，并求所需的最小操作次数。
如果无法合并为一个字符，则返回 -1。

简化规则举例：
假设颜色只有 'a' 和 'b'，合并规则为：

• 两个 'a' 合并为 'b'
• 两个 'b' 合并为 'a'
  则字符串 "aa" 可以合并为 'b'（1 次操作），字符串 "ab" 无法直接合并（相邻字符颜色不同），但可以通过先将 "aa" 合并为 'b' 等间接方式尝试。

解题思路

这是一个典型的区间动态规划问题，因为每次合并操作相当于将一段区间 [i, j] 合并为一个字符，而合并结果的颜色和操作次数取决于子区间的合并方式。

关键观察：

1. 最终要将整个区间 [0, n-1] 合并为一个字符，且这个字符可以是某种颜色 c。
2. 如果我们可以将区间 [i, j] 合并为颜色 c，那么需要知道最小操作次数。
3. 合并相邻相同颜色字符的规则可能允许“间接合并”：例如，"ab" 不能直接合并，但可以先将 "aa" 合并为 'b'，然后 'b' 和原来的 'b' 合并为 'a'。

动态规划定义

设 dp[i][j][c] 表示将子串 s[i..j] 合并为颜色 c 所需的最小操作次数。

• 如果不可能合并为颜色 c，则值为无穷大（INF）。
  颜色集合假设为有限种（例如小写字母 26 种）。

初始化：

• 对于长度为 1 的区间 [i, i]，如果 s[i] 的颜色是 c，则 dp[i][i][c] = 0（不需要操作），否则为 INF。

状态转移

考虑区间 [i, j]，我们想将其合并为颜色 c。
最后一步合并操作，一定是将 [i, j] 分成左右两个子区间，分别合并为颜色 c1 和 c2，且满足：c1 和 c2 可以合并为颜色 c（根据给定的合并规则）。
则操作次数 = 左子区间合并为 c1 的最小操作次数 + 右子区间合并为 c2 的最小操作次数 + 1（最后一步合并）。

所以状态转移方程为：

dp[i][j][c] = min{ dp[i][k][c1] + dp[k+1][j][c2] + 1 }

其中：

• k 是分割点，i ≤ k < j
• c1 和 c2 是任意两种颜色，且根据规则 merge(c1, c2) = c。

合并规则的处理

题目中合并规则可能以表格形式给出。例如：

合并规则表 mergeTable:
  'a' 和 'a' -> 'b'
  'b' 和 'b' -> 'a'
  'a' 和 'b' -> 不允许
  'b' 和 'a' -> 不允许

则只有当 c1 == c2 且 c1 为 'a' 或 'b' 时，才能合并为另一种颜色。

更一般地，我们可以预先构建一个映射：
mergeRules[c1][c2] 返回一个颜色列表，表示 c1 和 c2 合并后可以变成哪些颜色（可能多个，也可能没有）。

算法步骤

1. 初始化 dp 为 INF。
2. 对每个位置 i，dp[i][i][s[i]] = 0。
3. 枚举区间长度 len 从 2 到 n：
   • 枚举区间起点 i，则终点 j = i + len - 1。
   • 枚举分割点 k 从 i 到 j-1：
     • 枚举颜色 c1 和 c2，使得 dp[i][k][c1] 和 dp[k+1][j][c2] 均不是 INF。
     • 查合并规则表，得到 c1 和 c2 可以合并出的颜色列表 C。
     • 对每个 c in C，更新：

       dp[i][j][c] = min(dp[i][j][c], dp[i][k][c1] + dp[k+1][j][c2] + 1)
       

4. 最终答案：检查 dp[0][n-1][c] 对所有颜色 c 的最小值。如果全部为 INF，返回 -1，否则返回该最小值。

举例说明

假设字符串 s = "ab"，颜色只有 'a' 和 'b'，合并规则同上（相同颜色合并为另一种颜色，不同颜色不能合并）。

1. 初始化：
   • dp[0][0]['a'] = 0
   • dp[1][1]['b'] = 0
2. 区间 [0,1]：
   • 分割点 k=0：
     • 左区间 [0,0] 可合并为 'a'，右区间 [1,1] 可合并为 'b'。
     • 查规则：'a' 和 'b' 不能合并，无解。
   • 所以 dp[0][1][c] 均为 INF，无法合并为一个字符，返回 -1。

再例：s = "aa"，规则同上。

1. 初始化：
   • dp[0][0]['a'] = 0
   • dp[1][1]['a'] = 0
2. 区间 [0,1]：
   • 分割点 k=0：
     • 左区间 'a'，右区间 'a'，合并规则：两个 'a' 合并为 'b'。
     • 操作次数 = 0 + 0 + 1 = 1。
     • 所以 dp[0][1]['b'] = 1。
3. 最终答案：min(dp[0][1][c]) = 1（颜色为 'b'）。

复杂度分析

• 状态数：O(n^2 * m)，其中 m 是颜色种类数（例如 26）。
• 转移：枚举分割点 k 和颜色对 (c1, c2)，复杂度为 O(n^3 * m^2)。
• 在实际问题中，颜色种类通常很少（例如 2-4 种），所以可接受。

关键点总结

1. 区间 DP 状态表示：dp[i][j][c] 表示将区间合并为颜色 c 的最小操作次数。
2. 状态转移基于最后一次合并，将区间分为左右两部分，并查表判断合并结果颜色。
3. 最终答案是在 dp[0][n-1][c] 中取最小值。
4. 如果所有颜色均不可行，返回 -1。

这种方法可以处理任意合并规则（只要规则是确定的），并且保证了最小操作次数。