合并相邻字符形成目标串的最小操作次数问题（字符插入、删除、替换，带相邻相同合并规则与代价）

字数 6133 2025-12-24 20:04:33

合并相邻字符形成目标串的最小操作次数问题（字符插入、删除、替换，带相邻相同合并规则与代价）

题目描述

你有一个由小写字母组成的初始字符串 s，你可以对 s 进行以下操作任意次（每次操作有对应代价）：

插入：在任意位置插入一个小写字母，代价为 c_i。
删除：删除任意位置的字符，代价为 c_d。
替换：将任意位置的字符替换为另一个小写字母，代价为 c_r。
合并：如果两个相邻字符相同，可以选择将它们合并为一个新字符（新字符可以是任意小写字母，不一定与原字符相同），代价为 c_m。合并后原来两个字符消失，新字符占据原位置，字符串长度减 1。

你的目标是经过一系列操作，将初始字符串 s 转化为目标字符串 t。
求所需的最小总代价。

示例
假设初始串 s = "aab"，目标串 t = "ab"，代价为：c_i = 1, c_d = 1, c_r = 1, c_m = 1。
一种可能的操作序列：

将 s[0] 和 s[1] 合并（两个 'a'），合并为新字符 'a'，代价 1，得到 "ab"（此时已等于 t）。
总代价 = 1。
如果不用合并，可以通过删除一个 'a' 得到 "ab"，代价也是 1。
但若合并代价更低（比如 c_m = 0.5），则合并更优。

解题思路（循序渐进）

本题是字符串编辑距离的扩展，加入了“相邻相同合并”操作。
因为合并操作会改变字符串长度和字符，且依赖于相邻字符的相等性，必须用区间 DP 来跟踪子串的变化。

步骤 1：定义 DP 状态

设 dp[i][j][k][l] 表示将 s 的子串 s[i..j]（闭区间）转化为 t 的子串 t[k..l] 的最小代价。
但这样状态数可能太多（O(n^2 * m^2)），且合并操作会改变长度，不易处理。
我们换一种更高效的定义：

定义：dp[i][j][x][y] 表示将 s 的子串 s[i..j] 转化为 t 的子串 t[x..y] 的最小代价。
但这里我们注意：合并操作只发生在 s 的子串内部，不会涉及 t。
所以我们可以将状态设计为：
dp[i][j] 表示将 s[i..j] 转化为 任意一个字符 的最小代价（即合并到只剩一个字符）。
然后配合另一个 DP 数组 f[i][j][p][q] 表示将 s[i..j] 转化为 t[p..q] 的最小代价。

但更简洁的通用方法是：
dp[i][j][len_t] 表示将 s[i..j] 转化为 t 的某个长度为 len_t 的子串的最小代价。但这样不好直接对应到 t 的具体子串。

最终采用的标准方法：
设 f[i][j] 表示将 s 的子串 s[i..j] 转化为空串的最小代价（只通过删除和合并）。
设 g[i][j][p][q] 表示将 s[i..j] 转化为 t[p..q] 的最小代价。
但四维数组太大，可以优化：我们其实只需要将 s 的每个区间变成 t 的某个区间，因此可以用 dp[i][j][a][b] 表示将 s[i..j] 变成 t[a..b] 的最小代价。
但我们可以利用“合并”操作只在 s 上进行的特性，先预处理出 s 的每个区间合并成单个字符的最小代价，再用类似编辑距离的方式匹配到 t 的子串。

步骤 2：预处理合并代价

设 merge[i][j][ch] 表示将 s[i..j] 通过合并、删除、替换操作变成单个字符 ch 的最小代价。
但这样维度是 O(n^2 * 26)，在 n 较小时可接受。
我们可以用区间 DP 计算：
merge[i][j][ch] 初始化为：

如果 j == i，则代价是 min(c_r * (s[i] != ch), 0)，即如果相同则 0，否则替换代价。
如果 j > i，则考虑最后一步操作：
1. 删除 s[i]，然后 merge[i+1][j][ch] 加上删除代价 c_d。
2. 替换 s[i] 为某个字符 c'，代价为 c_r * (s[i] != c')，然后 merge[i+1][j][ch] 加上替换代价，但要考虑替换后是否可合并？这里替换后，s[i] 变为 c'，但 c' 和后面的串最终要合并成 ch，这需要更复杂的状态转移。

更优的方法是定义 h[i][j] 表示将 s[i..j] 合并为任意单个字符的最小代价，然后记录对应的字符。
但为了匹配 t，我们需要知道合并成具体字符 ch 的代价。
实际上我们可以在匹配时动态计算，因为合并操作只在相邻相同字符时发生。

简化处理：
我们可以在区间 DP 中，将“合并”看作一种操作，和删除、替换、插入并列。
但合并是特殊的，它要求两个相邻字符相同，且合并后产生的新字符可以任意。
因此我们设计状态：
cost[i][j][c] 表示将 s[i..j] 变成单个字符 c 的最小代价。
转移时，考虑最后一步：

如果 j == i，cost[i][i][c] = (s[i] == c ? 0 : c_r)。
如果 j > i，考虑将 s[i..j] 分成两段 s[i..k] 和 s[k+1..j]，分别变成字符 c1 和 c2，然后如果 c1 == c2，则可以合并为 c，代价为 cost[i][k][c1] + cost[k+1][j][c2] + (c == c1 ? 0 : c_r) + c_m，这里注意合并本身代价 c_m，且合并后如果 c1 不等于目标 c，则需要额外替换代价。
实际上更准确的合并规则：合并操作将两个相同字符合并为一个新字符，新字符可以任意，所以合并的代价是 c_m + (c == c1 ? 0 : c_r)。
但这样会复杂，因为 c1 和 c2 可能不同，此时不能直接合并，需要先通过替换使它们相同。

为了简化，我们可以在状态转移中，允许“替换”操作改变字符，因此我们可以在合并前先替换成相同字符。
标准转移方程（预处理 cost[i][j][c]）：
初始化：cost[i][i][c] = (s[i] == c ? 0 : c_r)。
对于长度 len 从 2 到 n：
cost[i][j][c] 先考虑直接删除、替换等操作，但更直接的方法是：

最后一步是删除 s[i]：cost[i][j][c] = min(cost[i][j][c], c_d + cost[i+1][j][c])。
最后一步是替换 s[i] 为 c'：代价 c_r*(s[i]!=c') + cost[i+1][j][c]，这里 c' 必须等于 c 吗？不一定，因为替换后 s[i] 变为 c'，后面子串变为单个字符 c，但 c' 和 c 可能不同，此时需要额外替换。其实更简单：替换 s[i] 为 c，代价 c_r*(s[i]!=c) + cost[i+1][j][c]。
最后一步是合并：将 s[i..j] 分成两段，分别变成相同字符 c'，然后合并为 c，代价为 cost[i][k][c'] + cost[k+1][j][c'] + c_m + (c'==c ? 0 : c_r)。这里注意，合并要求两段最终字符相同，即 c' 相同。
枚举 k 和 c' 即可。

cost 的维度过大时（n^2*26），但 n 较小（比如 ≤ 50）时可接受。

步骤 3：匹配到目标串 t

有了 cost[i][j][c] 后，我们定义 dp[i][j][a][b] 表示将 s[i..j] 变成 t[a..b] 的最小代价。
转移时，考虑 t[a..b] 的长度：

如果 a == b，则目标是一个字符 t[a]，那么 dp[i][j][a][a] = cost[i][j][t[a]]。
如果 a < b，考虑最后一步匹配：
1. 将 s[i..j] 的最后一个字符匹配到 t[b]：将 s 分成两段 s[i..k] 和 s[k+1..j]，前者变成 t[a..b-1]，后者变成单个字符 t[b]，代价为 dp[i][k][a][b-1] + cost[k+1][j][t[b]]。
2. 将 s[i..j] 的第一个字符匹配到 t[a]：类似分成两段。
  但更标准的方法是区间 DP 枚举分界点匹配目标串的某个分割点。

更好的方法是直接扩展编辑距离 DP：
设 f[i][j] 表示将 s[0..i] 变成 t[0..j] 的最小代价。但这样不能处理合并操作，因为合并会减少长度，且依赖于相邻字符。
所以必须用区间 DP 同时处理 s 和 t 的子串。

最终实用状态设计：
dp[l1][r1][l2][r2] 表示将 s[l1..r1] 变成 t[l2..r2] 的最小代价。
转移：

删除 s[l1]：dp[l1][r1][l2][r2] = min(dp[l1][r1][l2][r2], c_d + dp[l1+1][r1][l2][r2])。
插入字符匹配 t[l2]：dp[l1][r1][l2][r2] = min(dp[l1][r1][l2][r2], c_i + dp[l1][r1][l2+1][r2])。
替换 s[l1] 匹配 t[l2]：dp[l1][r1][l2][r2] = min(dp[l1][r1][l2][r2], c_r*(s[l1]!=t[l2]) + dp[l1+1][r1][l2+1][r2])。
合并操作：在 s[l1..r1] 中，如果某段 s[l1..k] 可以合并成一个字符，然后匹配 t[l2]，再匹配剩下的。但更一般地，合并操作是 s 内部操作，可以在 s 的区间内任意位置合并相邻相同字符。
为了处理合并，我们可以在 s 区间长度大于 1 时，枚举合并的分界点 k，将 s[l1..k] 和 s[k+1..r1] 分别匹配到 t 的子串，但要求 s[l1..k] 和 s[k+1..r1] 的最后一个字符相同，才能合并。
实际上，我们可以在 dp 转移中，用预处理好的 cost 来简化：
将 s[l1..r1] 的某一段 s[l1..k] 合并成一个字符 ch，然后匹配 t[l2]，代价为 cost[l1][k][ch] + (ch==t[l2]?0:c_r) + dp[k+1][r1][l2+1][r2]。

但这样仍然较复杂。常见简化是：不显式记录合并，而是允许“相邻相同合并”作为一步操作，在区间 DP 中，如果 s[i] == s[i+1]，则可以合并，代价为 c_m，合并成的新字符可以任意（通过额外替换代价调整）。

步骤 4：简化版解法（假设合并只合并相邻相同字符，且合并后字符与原字符相同）

假设合并操作只能将两个相同字符合并为相同字符（如 aa -> a），这样合并不会改变字符种类。
则合并相当于一种删除（删掉一个相同字符），但代价是 c_m 不是 c_d。
此时问题退化为普通编辑距离，但多了一种操作“合并相邻相同字符”，代价为 c_m。

定义 dp[i][j][a][b] 为将 s[i..j] 变成 t[a..b] 的最小代价。
转移：

删除 s[i]：c_d + dp[i+1][j][a][b]。
插入 t[a] 在开头：c_i + dp[i][j][a+1][b]。
替换 s[i] 为 t[a]：c_r*(s[i]!=t[a]) + dp[i+1][j][a+1][b]。
如果 i+1 <= j 且 s[i] == s[i+1]，则可以合并这两个字符（保留一个，删除另一个），代价为 c_m + dp[i+1][j][a][b]。

但这里合并后字符不变，所以相当于删掉一个相同字符，代价 c_m。
这样可以在普通编辑距离上稍作修改。

步骤 5：最终算法框架（假设合并后字符可不同，但需额外替换）

我们可以用记忆化搜索实现：
dfs(i, j, a, b) 表示将 s[i..j] 变成 t[a..b] 的最小代价。
转移：

如果 a > b 且 i > j，返回 0。
如果 a > b 但 i <= j，则需删除 s[i..j] 全部，代价为 (j-i+1)*c_d 或通过合并减少代价。
如果 i > j 但 a <= b，则需插入 t[a..b] 全部，代价为 (b-a+1)*c_i。
否则，考虑操作：
- 删除 s[i]：c_d + dfs(i+1, j, a, b)。
- 插入 t[a]：c_i + dfs(i, j, a+1, b)。
- 替换 s[i] 为 t[a]：c_r*(s[i]!=t[a]) + dfs(i+1, j, a+1, b)。
- 合并：枚举 k 从 i 到 j-1，如果 s[k] == s[k+1]，则可以合并，新字符任意，设合并后字符为 ch，则：
  代价 = c_m + (ch==t[a]?0:c_r) + dfs(新序列, a+1, b)。
  但“新序列”是去掉 s[k+1] 并将 s[k] 改为 ch 的序列。这需要改变字符串，不易直接 DP。

为了可计算，我们可以增加状态维度，记录当前 s[i..j] 的第一个字符是否是通过合并得到的。但这会变得很复杂。

竞赛中常见简化：
将“合并相邻相同字符”视为一种删除，代价为 c_m，但合并后字符不变。这样就可直接用普通编辑距离 DP 加上合并转移。

总结

这个问题是编辑距离的扩展，难点在于合并操作会改变字符且减少长度，导致状态转移复杂。
完整解法需要先预处理 cost[i][j][ch]，再用区间 DP 匹配到 t。
如果题目限制合并后字符必须与原字符相同，则问题简化为带合并删除操作的编辑距离，可用四维 DP 解决。
如果合并后字符可任意，则需增加字符维度，代价是状态数增加。

由于题目通常 n, m ≤ 20 或 30，四维 DP 加字符维度（26）在时间复杂度 O(n^2 * m^2 * 26) 可接受。

合并相邻字符形成目标串的最小操作次数问题（字符插入、删除、替换，带相邻相同合并规则与代价）题目描述你有一个由小写字母组成的初始字符串 s ，你可以对 s 进行以下操作任意次（每次操作有对应代价）：插入：在任意位置插入一个小写字母，代价为 c_i 。删除：删除任意位置的字符，代价为 c_d 。替换：将任意位置的字符替换为另一个小写字母，代价为 c_r 。合并：如果两个相邻字符相同，可以选择将它们合并为一个新字符（新字符可以是任意小写字母，不一定与原字符相同），代价为 c_m 。合并后原来两个字符消失，新字符占据原位置，字符串长度减 1。你的目标是经过一系列操作，将初始字符串 s 转化为目标字符串 t 。求所需的最小总代价。示例假设初始串 s = "aab" ，目标串 t = "ab" ，代价为： c_i = 1 , c_d = 1 , c_r = 1 , c_m = 1 。一种可能的操作序列：将 s[0] 和 s[1] 合并（两个 'a' ），合并为新字符 'a' ，代价 1，得到 "ab" （此时已等于 t ）。总代价 = 1。如果不用合并，可以通过删除一个 'a' 得到 "ab" ，代价也是 1。但若合并代价更低（比如 c_m = 0.5 ），则合并更优。解题思路（循序渐进）本题是字符串编辑距离的扩展，加入了“相邻相同合并”操作。因为合并操作会改变字符串长度和字符，且依赖于相邻字符的相等性，必须用区间 DP 来跟踪子串的变化。步骤 1：定义 DP 状态设 dp[i][j][k][l] 表示将 s 的子串 s[i..j] （闭区间）转化为 t 的子串 t[k..l] 的最小代价。但这样状态数可能太多（O(n^2 * m^2)），且合并操作会改变长度，不易处理。我们换一种更高效的定义：定义： dp[i][j][x][y] 表示将 s 的子串 s[i..j] 转化为 t 的子串 t[x..y] 的最小代价。但这里我们注意：合并操作只发生在 s 的子串内部，不会涉及 t 。所以我们可以将状态设计为： dp[i][j] 表示将 s[i..j] 转化为任意一个字符的最小代价（即合并到只剩一个字符）。然后配合另一个 DP 数组 f[i][j][p][q] 表示将 s[i..j] 转化为 t[p..q] 的最小代价。但更简洁的通用方法是： dp[i][j][len_t] 表示将 s[i..j] 转化为 t 的某个长度为 len_t 的子串的最小代价。但这样不好直接对应到 t 的具体子串。最终采用的标准方法：设 f[i][j] 表示将 s 的子串 s[i..j] 转化为空串的最小代价（只通过删除和合并）。设 g[i][j][p][q] 表示将 s[i..j] 转化为 t[p..q] 的最小代价。但四维数组太大，可以优化：我们其实只需要将 s 的每个区间变成 t 的某个区间，因此可以用 dp[i][j][a][b] 表示将 s[i..j] 变成 t[a..b] 的最小代价。但我们可以利用“合并”操作只在 s 上进行的特性，先预处理出 s 的每个区间合并成单个字符的最小代价，再用类似编辑距离的方式匹配到 t 的子串。步骤 2：预处理合并代价设 merge[i][j][ch] 表示将 s[i..j] 通过合并、删除、替换操作变成单个字符 ch 的最小代价。但这样维度是 O(n^2 * 26)，在 n 较小时可接受。我们可以用区间 DP 计算： merge[i][j][ch] 初始化为：如果 j == i ，则代价是 min(c_r * (s[i] != ch), 0) ，即如果相同则 0，否则替换代价。如果 j > i ，则考虑最后一步操作：删除 s[i] ，然后 merge[i+1][j][ch] 加上删除代价 c_d 。替换 s[i] 为某个字符 c' ，代价为 c_r * (s[i] != c') ，然后 merge[i+1][j][ch] 加上替换代价，但要考虑替换后是否可合并？这里替换后， s[i] 变为 c' ，但 c' 和后面的串最终要合并成 ch ，这需要更复杂的状态转移。更优的方法是定义 h[i][j] 表示将 s[i..j] 合并为任意单个字符的最小代价，然后记录对应的字符。但为了匹配 t ，我们需要知道合并成具体字符 ch 的代价。实际上我们可以在匹配时动态计算，因为合并操作只在相邻相同字符时发生。简化处理：我们可以在区间 DP 中，将“合并”看作一种操作，和删除、替换、插入并列。但合并是特殊的，它要求两个相邻字符相同，且合并后产生的新字符可以任意。因此我们设计状态： cost[i][j][c] 表示将 s[i..j] 变成单个字符 c 的最小代价。转移时，考虑最后一步：如果 j == i ， cost[i][i][c] = (s[i] == c ? 0 : c_r) 。如果 j > i ，考虑将 s[i..j] 分成两段 s[i..k] 和 s[k+1..j] ，分别变成字符 c1 和 c2 ，然后如果 c1 == c2 ，则可以合并为 c ，代价为 cost[i][k][c1] + cost[k+1][j][c2] + (c == c1 ? 0 : c_r) + c_m ，这里注意合并本身代价 c_m ，且合并后如果 c1 不等于目标 c ，则需要额外替换代价。实际上更准确的合并规则：合并操作将两个相同字符合并为一个新字符，新字符可以任意，所以合并的代价是 c_m + (c == c1 ? 0 : c_r) 。但这样会复杂，因为 c1 和 c2 可能不同，此时不能直接合并，需要先通过替换使它们相同。为了简化，我们可以在状态转移中，允许“替换”操作改变字符，因此我们可以在合并前先替换成相同字符。标准转移方程（预处理 cost[i][j][c] ）：初始化： cost[i][i][c] = (s[i] == c ? 0 : c_r) 。对于长度 len 从 2 到 n： cost[i][j][c] 先考虑直接删除、替换等操作，但更直接的方法是：最后一步是删除 s[i] ： cost[i][j][c] = min(cost[i][j][c], c_d + cost[i+1][j][c]) 。最后一步是替换 s[i] 为 c' ：代价 c_r*(s[i]!=c') + cost[i+1][j][c] ，这里 c' 必须等于 c 吗？不一定，因为替换后 s[i] 变为 c' ，后面子串变为单个字符 c ，但 c' 和 c 可能不同，此时需要额外替换。其实更简单：替换 s[i] 为 c ，代价 c_r*(s[i]!=c) + cost[i+1][j][c] 。最后一步是合并：将 s[i..j] 分成两段，分别变成相同字符 c' ，然后合并为 c ，代价为 cost[i][k][c'] + cost[k+1][j][c'] + c_m + (c'==c ? 0 : c_r) 。这里注意，合并要求两段最终字符相同，即 c' 相同。枚举 k 和 c' 即可。 cost 的维度过大时（n^2* 26），但 n 较小（比如 ≤ 50）时可接受。步骤 3：匹配到目标串 t 有了 cost[i][j][c] 后，我们定义 dp[i][j][a][b] 表示将 s[i..j] 变成 t[a..b] 的最小代价。转移时，考虑 t[a..b] 的长度：如果 a == b ，则目标是一个字符 t[a] ，那么 dp[i][j][a][a] = cost[i][j][t[a]] 。如果 a < b ，考虑最后一步匹配：将 s[i..j] 的最后一个字符匹配到 t[b] ：将 s 分成两段 s[i..k] 和 s[k+1..j] ，前者变成 t[a..b-1] ，后者变成单个字符 t[b] ，代价为 dp[i][k][a][b-1] + cost[k+1][j][t[b]] 。将 s[i..j] 的第一个字符匹配到 t[a] ：类似分成两段。但更标准的方法是区间 DP 枚举分界点匹配目标串的某个分割点。更好的方法是直接扩展编辑距离 DP：设 f[i][j] 表示将 s[0..i] 变成 t[0..j] 的最小代价。但这样不能处理合并操作，因为合并会减少长度，且依赖于相邻字符。所以必须用区间 DP 同时处理 s 和 t 的子串。最终实用状态设计： dp[l1][r1][l2][r2] 表示将 s[l1..r1] 变成 t[l2..r2] 的最小代价。转移：删除 s[l1] ： dp[l1][r1][l2][r2] = min(dp[l1][r1][l2][r2], c_d + dp[l1+1][r1][l2][r2]) 。插入字符匹配 t[l2] ： dp[l1][r1][l2][r2] = min(dp[l1][r1][l2][r2], c_i + dp[l1][r1][l2+1][r2]) 。替换 s[l1] 匹配 t[l2] ： dp[l1][r1][l2][r2] = min(dp[l1][r1][l2][r2], c_r*(s[l1]!=t[l2]) + dp[l1+1][r1][l2+1][r2]) 。合并操作：在 s[l1..r1] 中，如果某段 s[l1..k] 可以合并成一个字符，然后匹配 t[l2] ，再匹配剩下的。但更一般地，合并操作是 s 内部操作，可以在 s 的区间内任意位置合并相邻相同字符。为了处理合并，我们可以在 s 区间长度大于 1 时，枚举合并的分界点 k ，将 s[l1..k] 和 s[k+1..r1] 分别匹配到 t 的子串，但要求 s[l1..k] 和 s[k+1..r1] 的最后一个字符相同，才能合并。实际上，我们可以在 dp 转移中，用预处理好的 cost 来简化：将 s[l1..r1] 的某一段 s[l1..k] 合并成一个字符 ch ，然后匹配 t[l2] ，代价为 cost[l1][k][ch] + (ch==t[l2]?0:c_r) + dp[k+1][r1][l2+1][r2] 。但这样仍然较复杂。常见简化是：不显式记录合并，而是允许“相邻相同合并”作为一步操作，在区间 DP 中，如果 s[i] == s[i+1] ，则可以合并，代价为 c_m ，合并成的新字符可以任意（通过额外替换代价调整）。步骤 4：简化版解法（假设合并只合并相邻相同字符，且合并后字符与原字符相同）假设合并操作只能将两个相同字符合并为相同字符（如 aa -> a ），这样合并不会改变字符种类。则合并相当于一种删除（删掉一个相同字符），但代价是 c_m 不是 c_d 。此时问题退化为普通编辑距离，但多了一种操作“合并相邻相同字符”，代价为 c_m 。定义 dp[i][j][a][b] 为将 s[i..j] 变成 t[a..b] 的最小代价。转移：删除 s[i] ： c_d + dp[i+1][j][a][b] 。插入 t[a] 在开头： c_i + dp[i][j][a+1][b] 。替换 s[i] 为 t[a] ： c_r*(s[i]!=t[a]) + dp[i+1][j][a+1][b] 。如果 i+1 <= j 且 s[i] == s[i+1] ，则可以合并这两个字符（保留一个，删除另一个），代价为 c_m + dp[i+1][j][a][b] 。但这里合并后字符不变，所以相当于删掉一个相同字符，代价 c_m 。这样可以在普通编辑距离上稍作修改。步骤 5：最终算法框架（假设合并后字符可不同，但需额外替换）我们可以用记忆化搜索实现： dfs(i, j, a, b) 表示将 s[i..j] 变成 t[a..b] 的最小代价。转移：如果 a > b 且 i > j ，返回 0。如果 a > b 但 i <= j ，则需删除 s[i..j] 全部，代价为 (j-i+1)*c_d 或通过合并减少代价。如果 i > j 但 a <= b ，则需插入 t[a..b] 全部，代价为 (b-a+1)*c_i 。否则，考虑操作：删除 s[i] ： c_d + dfs(i+1, j, a, b) 。插入 t[a] ： c_i + dfs(i, j, a+1, b) 。替换 s[i] 为 t[a] ： c_r*(s[i]!=t[a]) + dfs(i+1, j, a+1, b) 。合并：枚举 k 从 i 到 j-1 ，如果 s[k] == s[k+1] ，则可以合并，新字符任意，设合并后字符为 ch ，则：代价 = c_m + (ch==t[a]?0:c_r) + dfs(新序列, a+1, b) 。但“新序列”是去掉 s[k+1] 并将 s[k] 改为 ch 的序列。这需要改变字符串，不易直接 DP。为了可计算，我们可以增加状态维度，记录当前 s[i..j] 的第一个字符是否是通过合并得到的。但这会变得很复杂。竞赛中常见简化：将“合并相邻相同字符”视为一种删除，代价为 c_m ，但合并后字符不变。这样就可直接用普通编辑距离 DP 加上合并转移。总结这个问题是编辑距离的扩展，难点在于合并操作会改变字符且减少长度，导致状态转移复杂。完整解法需要先预处理 cost[i][j][ch] ，再用区间 DP 匹配到 t 。如果题目限制合并后字符必须与原字符相同，则问题简化为带合并删除操作的编辑距离，可用四维 DP 解决。如果合并后字符可任意，则需增加字符维度，代价是状态数增加。由于题目通常 n, m ≤ 20 或 30，四维 DP 加字符维度（26）在时间复杂度 O(n^2 * m^2 * 26) 可接受。