合并相邻字符形成目标串的最小操作次数问题（字符插入、删除、替换）
题目描述
给定两个字符串 source 和 target，你可以对 source 执行三种操作，每种操作都有不同的成本：
- 插入一个字符，成本为
ins_cost。 - 删除一个字符，成本为
del_cost。 - 替换一个字符（将
source中的某个字符改为另一个字符），成本为rep_cost。
要求将 source 转换为 target 所需的最小总成本。
注意：插入、删除、替换操作可以在字符串的任意位置进行，且每次操作只针对一个字符。
问题分析
这本质上是一个编辑距离（Edit Distance）问题，不过我们这里将采用区间动态规划的视角来拆解，以帮助你更透彻地理解状态是如何在子区间上定义的。
我们考虑将 source 和 target 分别划分为子区间，并尝试逐步匹配它们。
动态规划思路
我们定义：
- 设
s的长度为m，t的长度为n。 - 定义
dp[i][j]表示将source的前i个字符（即s[0..i-1]）转换为target的前j个字符（即t[0..j-1]）所需的最小成本。- 注意：
i和j分别表示已考虑的字符数量，可以是 0（空串）。
- 注意：
- 最终答案：
dp[m][n]。
状态转移推导
我们要计算 dp[i][j]，考虑最后一步操作：
-
删除操作：
从source的前i个字符中删除最后一个字符s[i-1]，然后前i-1个字符需匹配target的前j个字符。- 状态转移：
dp[i][j] = dp[i-1][j] + del_cost。
- 状态转移：
-
插入操作：
在source的前i个字符后插入一个字符t[j-1]，使前i个字符能匹配target的前j-1个字符。- 状态转移：
dp[i][j] = dp[i][j-1] + ins_cost。
- 状态转移：
-
替换操作：
将source的第i个字符s[i-1]替换为target的第j个字符t[j-1]。- 如果
s[i-1] == t[j-1]，则无需替换，成本为 0。 - 否则成本为
rep_cost。 - 状态转移：
dp[i][j] = dp[i-1][j-1] + (s[i-1] == t[j-1] ? 0 : rep_cost)。
- 如果
综上，状态转移方程为：
\[dp[i][j] = \min \begin{cases} dp[i-1][j] + del\_cost, \\ dp[i][j-1] + ins\_cost, \\ dp[i-1][j-1] + (s[i-1] == t[j-1] \ ? \ 0 : rep\_cost) \end{cases} \]
边界条件（Base Cases）
- 当
i = 0且j = 0时，两个空串匹配，成本为 0：dp[0][0] = 0。 - 当
i = 0但j > 0时，source为空，只能不断插入字符来匹配target的前j个字符：
\[ dp[0][j] = j \times ins\_cost \]
- 当
i > 0但j = 0时，target为空，只能不断删除source的前i个字符：
\[ dp[i][0] = i \times del\_cost \]
示例演算
假设：
source = "abc",target = "abdc"ins_cost = 1,del_cost = 1,rep_cost = 1
我们逐步填表（dp 表尺寸为 (m+1) x (n+1)，即 4x5）：
- 初始化：
dp[0][0] = 0- 第一行：
dp[0][j] = j（全插入） - 第一列：
dp[i][0] = i（全删除）
初始表：
i\j 0 1 2 3 4
"" a b d c
0 "" 0 1 2 3 4
1 a 1
2 b 2
3 c 3
-
计算
dp[1][1]：- 删除：
dp[0][1] + 1 = 1+1=2 - 插入：
dp[1][0] + 1 = 1+1=2 - 替换：
dp[0][0] + (a==a?0:1) = 0+0=0
→ 取最小值 0，dp[1][1]=0
- 删除：
-
类似计算其他位置，完整表如下（过程略）：
最终表：
i\j 0 1 2 3 4
0 "" 0 1 2 3 4
1 a 1 0 1 2 3
2 b 2 1 0 1 2
3 c 3 2 1 1 1
结果：dp[3][4] = 1，表示最小成本为 1（只需在 "ab" 和 "c" 之间插入 'd' 即可）。
复杂度分析
- 时间复杂度：O(m × n)，因为要填充一个 (m+1) × (n+1) 的表格。
- 空间复杂度：O(m × n) 用于存储整个表格。但可以优化为 O(min(m, n))，因为计算
dp[i][j]时只依赖于上一行和当前行的前一个位置。
关键点总结
- 定义
dp[i][j]为子问题：从source的前i个字符到target的前j个字符的最小成本。 - 状态转移考虑最后一步操作的三种可能：删除、插入、替换。
- 边界条件处理空串的转换。
- 这个模型是编辑距离的标准动态规划解法，是区间DP的一个经典应用（将字符串看作区间，逐步匹配子区间）。
如果需要，我可以再给你一个不同的题目，比如**“合并相邻同色字符形成新字符的最小操作次数”**（带颜色变化规则），这也是区间DP的有趣变体。