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

字数 3753 2025-12-14 13:00:28

问题描述

给定一个字符串 s，长度为 n，其中每个字符有一个颜色（例如用小写字母 'a' 到 'z' 表示）。你可以重复执行以下操作：

选择两个相邻且颜色相同的字符（假设颜色为 c）。
将它们合并成一个新字符，新字符的颜色由规则表给出（不一定与 c 相同），这次操作的操作次数（成本）由成本表给出。

具体地，有一个规则表 rule[color1][color2] 表示：当两个颜色相同的字符（均为 color1）合并时，产生的新字符的颜色为 rule[color1][color1]（注意，这里规则通常只定义相同颜色的合并，因为只有相邻且颜色相同的字符才能合并）。同时，有一个成本表 cost[color1][color2] 表示合并两个颜色为 color1 的字符所需的操作次数（这里同样 color1 == color2）。

注意：规则表和成本表通常是预先给定的，且可能对不同的颜色对有不同的规则和成本。此外，规则表中可能包含不同颜色合并的规则，但本问题中只有相邻且颜色相同的字符才能合并，因此我们只用到对角线上的规则和成本。

目标：通过一系列合并操作，最终将整个字符串合并成一个字符，求所需的最小总操作次数（即最小成本）。如果无法合并成一个字符，则返回 -1。

解题思路

这个问题是区间动态规划的典型应用，因为合并操作只涉及相邻的字符，并且每次合并后区间长度减少。我们可以定义 dp[i][j][c] 表示将子串 s[i..j] 合并成单个颜色为 c 的字符所需的最小操作次数。如果无法合并成颜色 c，则值为无穷大。

状态转移时，考虑最后一次合并操作：将区间 [i, j] 分成左右两部分 [i, k] 和 [k+1, j]，分别合并成颜色 c1 和 c2，然后如果 c1 == c2，则可以将它们合并成新颜色 rule[c1][c1]，且花费 cost[c1][c1]。但这里有一个关键：我们可能通过多次合并使得左右两部分分别变成某种颜色，而最后一步合并要求左右两部分的颜色相同。

因此状态转移方程为：

\[dp[i][j][c] = \min_{\substack{i \le k < j \\ c1, c2}} \{ dp[i][k][c1] + dp[k+1][j][c2] + (c1 == c2 ? cost[c1][c1] : \infty) \} \]

其中，如果 c1 == c2，则合并后的颜色应为 rule[c1][c1]，我们需要检查这个颜色是否等于 c。如果相等，则更新 dp[i][j][c]。

但这样转移效率较低，因为需要枚举 c1 和 c2。我们可以优化：实际上，我们只关心左右两部分合并成相同颜色的情况，因为只有颜色相同才能合并。因此，我们可以先计算每个区间合并成任意颜色的最小成本，再在合并时检查颜色。

更高效的方法是：定义 dp[i][j] 为一个数组或字典，记录将区间 [i, j] 合并成各种颜色所需的最小成本。但为了简化，我们通常用三维 DP，颜色种类有限（比如 26 种）。

步骤概述：

定义状态：dp[i][j][c] 表示子串 s[i..j] 合并成颜色 c 的最小成本。
初始化：对于长度为 1 的区间 [i, i]，如果字符 s[i] 的颜色是 c0，则 dp[i][i][c0] = 0，其他颜色为无穷大。
状态转移：枚举区间长度 len 从 2 到 n，枚举左端点 i，右端点 j = i+len-1，枚举分割点 k，枚举左右两区间可能的颜色 c1 和 c2。如果 c1 == c2，则合并后颜色为 newC = rule[c1][c1]，合并成本为 cost[c1][c1]，那么：

\[ dp[i][j][newC] = \min(dp[i][j][newC], dp[i][k][c1] + dp[k+1][j][c2] + cost[c1][c1]) \]

最终答案：查看 dp[0][n-1][c] 对所有颜色 c 的最小值。如果全为无穷大，则返回 -1，否则返回最小值。

详细步骤

假设颜色种类数为 m（比如 26），字符颜色用 0 到 m-1 的整数表示。

输入处理：
- 字符串 s，长度为 n。
- 规则表 rule[m][m]，其中 rule[a][b] 表示两个颜色 a 和 b 合并后的颜色（但本问题中只用到 rule[a][a]）。
- 成本表 cost[m][m]，其中 cost[a][b] 表示合并颜色 a 和 b 的成本（本问题中只用到 cost[a][a]）。
初始化 DP 表：
- 创建一个三维数组 dp[n][n][m]，初始值为无穷大（表示不可行）。
- 对于每个位置 i，设 color = s[i] 对应的颜色编号，则 dp[i][i][color] = 0。
区间长度递增计算：
- 对于长度 len 从 2 到 n：
  - 对于左端点 i 从 0 到 n-len：
    - 设右端点 j = i + len - 1。
    - 对于分割点 k 从 i 到 j-1：
      - 对于颜色 c1 从 0 到 m-1：
        
        如果 dp[i][k][c1] 是无穷大，跳过。
        
        对于颜色 c2 从 0 到 m-1：
        
        如果 dp[k+1][j][c2] 是无穷大，跳过。
        
        如果 c1 != c2，则不能合并，跳过。
        
        计算合并后的颜色 newC = rule[c1][c1]。
        
        计算总成本 total = dp[i][k][c1] + dp[k+1][j][c2] + cost[c1][c1]。
        
        如果 total < dp[i][j][newC]，更新 dp[i][j][newC] = total。
获取答案：
- 在 dp[0][n-1][c] 中找到最小值 ans。
- 如果 ans 为无穷大，返回 -1，否则返回 ans。

时间复杂度

状态数：O(n² * m)，其中 m 是颜色数（通常较小，比如 26）。
转移：对于每个状态，需要枚举分割点和颜色，复杂度 O(n * m²)。
总复杂度：O(n³ * m²)。当 n 较大时可能较慢，但通常题目中 n 不超过 100，m 不超过 26，可以接受。

示例说明

假设字符串 s = "aabb"，颜色映射：'a' -> 0, 'b' -> 1，规则和成本如下：

rule[0][0] = 1（两个 'a' 合并成 'b'），cost[0][0] = 2
rule[1][1] = 0（两个 'b' 合并成 'a'），cost[1][1] = 3

初始：dp[0][0][0]=0, dp[1][1][0]=0, dp[2][2][1]=0, dp[3][3][1]=0。

长度 2：

区间 [0,1]：颜色相同（0），合并成 1，成本 2 → dp[0][1][1] = 2
区间 [2,3]：颜色相同（1），合并成 0，成本 3 → dp[2][3][0] = 3

长度 4（区间 [0,3]）：

分割点 k=1：左区间 [0,1] 可合并成颜色 1（成本 2），右区间 [2,3] 可合并成颜色 0（成本 3），颜色不同，不能合并。
分割点 k=0：左区间 [0,0] 颜色 0（成本 0），右区间 [1,3] 需要计算：
- 先计算区间 [1,3]：长度 3，可分割为 [1,1] 和 [2,3] 或 [1,2] 和 [3,3]。
- 这里简化，最终可计算出 dp[1][3][0] = 5（路径：先合并 [2,3] 成 0 成本 3，然后 [1,1] 颜色 0 和 [2,3] 颜色 0 合并，颜色相同（0）合并成 1，成本 2，总 5）。
- 那么左颜色 0，右颜色 0，相同，合并成 1，成本 2 → 总成本 0+5+2=7，得到 dp[0][3][1] = 7。
其他分割点类似，最终最小成本为 7，合并成颜色 1。

因此答案为 7。

优化提示

如果规则和成本只依赖于一种颜色，可以简化状态转移，只枚举一种颜色。
可以使用记忆化搜索（递归+缓存）简化实现。
当颜色种类多时，注意复杂度，但通常 m 较小。

总结

这个问题通过区间 DP 模拟合并过程，关键点是状态定义为区间合并成特定颜色的最小成本，转移时需确保左右区间合并后的颜色相同才能进行最后一次合并。通过枚举分割点和颜色，逐步计算出整个字符串合并的最小成本。

合并相邻同色字符的最小操作次数问题（每次操作可以合并两个相邻且颜色相同的字符，合并后生成一个新字符，且新字符颜色可能变化，并产生一定操作次数消耗，求将整个字符串合并为一个字符的最小操作次数）问题描述给定一个字符串 s ，长度为 n ，其中每个字符有一个颜色（例如用小写字母 'a' 到 'z' 表示）。你可以重复执行以下操作：选择两个相邻且颜色相同的字符（假设颜色为 c ）。将它们合并成一个新字符，新字符的颜色由规则表给出（不一定与 c 相同），这次操作的操作次数（成本）由成本表给出。具体地，有一个规则表 rule[color1][color2] 表示：当两个颜色相同的字符（均为 color1 ）合并时，产生的新字符的颜色为 rule[color1][color1] （注意，这里规则通常只定义相同颜色的合并，因为只有相邻且颜色相同的字符才能合并）。同时，有一个成本表 cost[color1][color2] 表示合并两个颜色为 color1 的字符所需的操作次数（这里同样 color1 == color2 ）。注意：规则表和成本表通常是预先给定的，且可能对不同的颜色对有不同的规则和成本。此外，规则表中可能包含不同颜色合并的规则，但本问题中只有相邻且颜色相同的字符才能合并，因此我们只用到对角线上的规则和成本。目标：通过一系列合并操作，最终将整个字符串合并成一个字符，求所需的最小总操作次数（即最小成本）。如果无法合并成一个字符，则返回 -1。解题思路这个问题是区间动态规划的典型应用，因为合并操作只涉及相邻的字符，并且每次合并后区间长度减少。我们可以定义 dp[i][j][c] 表示将子串 s[i..j] 合并成单个颜色为 c 的字符所需的最小操作次数。如果无法合并成颜色 c ，则值为无穷大。状态转移时，考虑最后一次合并操作：将区间 [i, j] 分成左右两部分 [i, k] 和 [k+1, j] ，分别合并成颜色 c1 和 c2 ，然后如果 c1 == c2 ，则可以将它们合并成新颜色 rule[c1][c1] ，且花费 cost[c1][c1] 。但这里有一个关键：我们可能通过多次合并使得左右两部分分别变成某种颜色，而最后一步合并要求左右两部分的颜色相同。因此状态转移方程为： \[ dp[ i][ j][ c] = \min_ {\substack{i \le k < j \\ c1, c2}} \{ dp[ i][ k][ c1] + dp[ k+1][ j][ c2] + (c1 == c2 ? cost[ c1][ c1 ] : \infty) \} \] 其中，如果 c1 == c2 ，则合并后的颜色应为 rule[c1][c1] ，我们需要检查这个颜色是否等于 c 。如果相等，则更新 dp[i][j][c] 。但这样转移效率较低，因为需要枚举 c1 和 c2 。我们可以优化：实际上，我们只关心左右两部分合并成相同颜色的情况，因为只有颜色相同才能合并。因此，我们可以先计算每个区间合并成任意颜色的最小成本，再在合并时检查颜色。更高效的方法是：定义 dp[i][j] 为一个数组或字典，记录将区间 [i, j] 合并成各种颜色所需的最小成本。但为了简化，我们通常用三维 DP，颜色种类有限（比如 26 种）。步骤概述：定义状态： dp[i][j][c] 表示子串 s[i..j] 合并成颜色 c 的最小成本。初始化：对于长度为 1 的区间 [i, i] ，如果字符 s[i] 的颜色是 c0 ，则 dp[i][i][c0] = 0 ，其他颜色为无穷大。状态转移：枚举区间长度 len 从 2 到 n ，枚举左端点 i ，右端点 j = i+len-1 ，枚举分割点 k ，枚举左右两区间可能的颜色 c1 和 c2 。如果 c1 == c2 ，则合并后颜色为 newC = rule[c1][c1] ，合并成本为 cost[c1][c1] ，那么： \[ dp[ i][ j][ newC] = \min(dp[ i][ j][ newC], dp[ i][ k][ c1] + dp[ k+1][ j][ c2] + cost[ c1][ c1 ]) \] 最终答案：查看 dp[0][n-1][c] 对所有颜色 c 的最小值。如果全为无穷大，则返回 -1，否则返回最小值。详细步骤假设颜色种类数为 m （比如 26），字符颜色用 0 到 m-1 的整数表示。输入处理：字符串 s ，长度为 n 。规则表 rule[m][m] ，其中 rule[a][b] 表示两个颜色 a 和 b 合并后的颜色（但本问题中只用到 rule[a][a] ）。成本表 cost[m][m] ，其中 cost[a][b] 表示合并颜色 a 和 b 的成本（本问题中只用到 cost[a][a] ）。初始化 DP 表：创建一个三维数组 dp[n][n][m] ，初始值为无穷大（表示不可行）。对于每个位置 i ，设 color = s[i] 对应的颜色编号，则 dp[i][i][color] = 0 。区间长度递增计算：对于长度 len 从 2 到 n ：对于左端点 i 从 0 到 n-len ：设右端点 j = i + len - 1 。对于分割点 k 从 i 到 j-1 ：对于颜色 c1 从 0 到 m-1：如果 dp[i][k][c1] 是无穷大，跳过。对于颜色 c2 从 0 到 m-1：如果 dp[k+1][j][c2] 是无穷大，跳过。如果 c1 != c2 ，则不能合并，跳过。计算合并后的颜色 newC = rule[c1][c1] 。计算总成本 total = dp[i][k][c1] + dp[k+1][j][c2] + cost[c1][c1] 。如果 total < dp[i][j][newC] ，更新 dp[i][j][newC] = total 。获取答案：在 dp[0][n-1][c] 中找到最小值 ans 。如果 ans 为无穷大，返回 -1，否则返回 ans 。时间复杂度状态数：O(n² * m)，其中 m 是颜色数（通常较小，比如 26）。转移：对于每个状态，需要枚举分割点和颜色，复杂度 O(n * m²)。总复杂度：O(n³ * m²)。当 n 较大时可能较慢，但通常题目中 n 不超过 100，m 不超过 26，可以接受。示例说明假设字符串 s = "aabb" ，颜色映射：'a' -> 0, 'b' -> 1，规则和成本如下： rule[0][0] = 1 （两个 'a' 合并成 'b'）， cost[0][0] = 2 rule[1][1] = 0 （两个 'b' 合并成 'a'）， cost[1][1] = 3 初始： dp[0][0][0]=0 , dp[1][1][0]=0 , dp[2][2][1]=0 , dp[3][3][1]=0 。长度 2：区间 [ 0,1]：颜色相同（0），合并成 1，成本 2 → dp[0][1][1] = 2 区间 [ 2,3]：颜色相同（1），合并成 0，成本 3 → dp[2][3][0] = 3 长度 4（区间 [ 0,3 ]）：分割点 k=1：左区间 [ 0,1] 可合并成颜色 1（成本 2），右区间 [ 2,3 ] 可合并成颜色 0（成本 3），颜色不同，不能合并。分割点 k=0：左区间 [ 0,0] 颜色 0（成本 0），右区间 [ 1,3 ] 需要计算：先计算区间 [ 1,3]：长度 3，可分割为 [ 1,1] 和 [ 2,3] 或 [ 1,2] 和 [ 3,3 ]。这里简化，最终可计算出 dp[1][3][0] = 5 （路径：先合并 [ 2,3] 成 0 成本 3，然后 [ 1,1] 颜色 0 和 [ 2,3 ] 颜色 0 合并，颜色相同（0）合并成 1，成本 2，总 5）。那么左颜色 0，右颜色 0，相同，合并成 1，成本 2 → 总成本 0+5+2=7，得到 dp[0][3][1] = 7 。其他分割点类似，最终最小成本为 7，合并成颜色 1。因此答案为 7。优化提示如果规则和成本只依赖于一种颜色，可以简化状态转移，只枚举一种颜色。可以使用记忆化搜索（递归+缓存）简化实现。当颜色种类多时，注意复杂度，但通常 m 较小。总结这个问题通过区间 DP 模拟合并过程，关键点是状态定义为区间合并成特定颜色的最小成本，转移时需确保左右区间合并后的颜色相同才能进行最后一次合并。通过枚举分割点和颜色，逐步计算出整个字符串合并的最小成本。