合并相邻字符形成目标串的最小操作次数问题（字符插入、删除、替换）

题目描述

给定两个字符串 source 和 target，以及三种操作的成本：

• 插入（I）：在 source 的任意位置插入一个字符，成本为 insertCost。
• 删除（D）：删除 source 中的一个字符，成本为 deleteCost。
• 替换（R）：将 source 中的一个字符替换为另一个字符，成本为 replaceCost。

你可以对 source 执行任意次上述操作（每次操作都会改变 source），目标是使 source 最终变成 target，并最小化总操作成本。注意，操作可以在任意位置进行，且每次操作后字符串长度可能变化。

输入

• 字符串 source 和 target，长度分别为 n 和 m。
• 整数 insertCost、deleteCost、replaceCost（均为非负值）。

输出

• 最小总成本。

例子

source = "abc"
target = "adc"
insertCost = 1
deleteCost = 1
replaceCost = 2

解释：将 'b' 替换为 'd'，成本=2，故最小总成本=2。

解题思路

这是一个经典的编辑距离（Edit Distance）问题，但通常编辑距离的 DP 定义是基于 source[0..i] 到 target[0..j] 的最小成本。我们可以用区间 DP 的视角来理解：状态 dp[i][j] 表示将 source 的前 i 个字符（子串 source[0..i-1]）转换成 target 的前 j 个字符（子串 target[0..j-1]）的最小成本。注意：这里“前 i 个字符”指的是长度为 i 的前缀。

由于操作可以在任意位置进行，我们可以从最后一个字符的匹配情况来考虑状态转移。

详细步骤

1. 定义状态

令 dp[i][j] 表示将 source 的前 i 个字符转换为 target 的前 j 个字符的最小成本。

• i 的范围是 0 到 n（i=0 表示 source 前缀为空串）。
• j 的范围是 0 到 m（j=0 表示 target 前缀为空串）。

2. 初始条件

• dp[0][0] = 0：两个空串转换成本为 0。
• dp[i][0] = i * deleteCost：将 source 的前 i 个字符全部删除，成本为 i 次删除。
• dp[0][j] = j * insertCost：空串通过插入 j 次变成 target 的前 j 个字符。

3. 状态转移方程

考虑如何从 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] 转移到 dp[i][j]。

对于 source 的第 i 个字符 srcChar = source[i-1] 和 target 的第 j 个字符 tarChar = target[j-1]：

1. 替换操作：将 srcChar 替换为 tarChar。
   • 如果 srcChar == tarChar，则不需要替换，成本 = dp[i-1][j-1]。
   • 否则，成本 = dp[i-1][j-1] + replaceCost。
2. 删除操作：删除 srcChar，然后需要将 source 的前 i-1 个字符转换成 target 的前 j 个字符。
   • 成本 = dp[i-1][j] + deleteCost。
3. 插入操作：在 source 的第 i 个位置（实际上是已处理完前 i 个字符后）插入 tarChar，然后需要将 source 的前 i 个字符转换成 target 的前 j-1 个字符。
   • 成本 = dp[i][j-1] + insertCost。

因此，状态转移方程为：

如果 srcChar == tarChar:
    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j] + deleteCost, dp[i][j-1] + insertCost)
否则：
    dp[i][j] = min(dp[i-1][j-1] + replaceCost, dp[i-1][j] + deleteCost, dp[i][j-1] + insertCost)

4. 计算顺序

按照 i 从 1 到 n，j 从 1 到 m 的顺序计算 dp[i][j]，确保依赖的子问题都已经计算过。

5. 最终答案

dp[n][m] 即为将整个 source 转换成 target 的最小成本。

示例演算

以 source = "abc", target = "adc", insertCost = 1, deleteCost = 1, replaceCost = 2 为例。

初始化 dp 表（行 i 对应 source 前缀长度，列 j 对应 target 前缀长度）：

i\j | 0  1  2  3
----------------
0   | 0  1  2  3
1   | 1  ?  ?  ?
2   | 2  ?  ?  ?
3   | 3  ?  ?  ?

dp[1][1]：source[0]='a', target[0]='a'，字符相同。

• 替换（实际不需替换）：dp[0][0] + 0 = 0
• 删除：dp[0][1] + 1 = 1+1=2
• 插入：dp[1][0] + 1 = 1+1=2
  取最小值 0，所以 dp[1][1]=0。

dp[1][2]：source[0]='a', target[1]='d'，字符不同。

• 替换：dp[0][1] + 2 = 1+2=3
• 删除：dp[0][2] + 1 = 2+1=3
• 插入：dp[1][1] + 1 = 0+1=1
  取最小值 1，所以 dp[1][2]=1。

dp[1][3]：source[0]='a', target[2]='c'，字符不同。

• 替换：dp[0][2] + 2 = 2+2=4
• 删除：dp[0][3] + 1 = 3+1=4
• 插入：dp[1][2] + 1 = 1+1=2
  取最小值 2，所以 dp[1][3]=2。

继续计算，最终得到：

i\j | 0  1  2  3
----------------
0   | 0  1  2  3
1   | 1  0  1  2
2   | 2  1  2  3
3   | 3  2  3  2

dp[3][3]=2 即为答案，对应替换 'b' 为 'd'（成本 2），其他字符不变。

复杂度分析

• 时间复杂度：O(n*m)，因为需要填充一个 (n+1)*(m+1) 的 DP 表。
• 空间复杂度：O(n*m)。可以优化到 O(min(n,m)) 使用滚动数组，但这里为了清晰展示保留二维。

关键点

• 状态 dp[i][j] 表示前缀之间的转换，而非子串任意区间。
• 三种操作对应三种状态转移方向：替换（左上）、删除（上方）、插入（左方）。
• 当字符相同时，替换成本为 0，即直接继承 dp[i-1][j-1]。

这个问题是区间 DP 的一种线性序列比对形式，广泛应用于文本比较、DNA序列对齐等领域。