区间动态规划例题：最小代价合并字符串形成目标字符串
问题描述
我们有两个字符串 source 和 target，它们的长度分别为 n 和 m。我们希望通过一系列操作将 source 转换为 target。允许的操作有两种：
- 插入字符：在当前字符串的任意位置插入任意字符，每次插入的成本为
insertCost。 - 删除字符：删除当前字符串中的任意字符，每次删除的成本为
deleteCost。
我们的目标是找到将 source 完全转换为 target 的最小总成本。
输入：
- 字符串
source和target，长度分别为n和m（长度范围通常在 1 到 500 之间）。 - 插入成本
insertCost（整数，大于等于 0）。 - 删除成本
deleteCost（整数，大于等于 0）。
输出：一个整数，表示最小总成本。
示例：
- source = "abcd", target = "acd", insertCost = 1, deleteCost = 1。
最小成本为 2：删除 'b'（成本1），然后在 'c' 后插入 'd'（成本1）？不，这里其实更简单：只需删除 'b' 即可将 "abcd" 变成 "acd"，但 "acd" 中 'd' 的位置？让我们仔细分析：source = "a b c d"，target = "a c d"。对应关系是：
source[0]='a' -> target[0]='a' (匹配)
source[1]='b' -> 需要删除 (成本1)
source[2]='c' -> target[1]='c' (匹配)
source[3]='d' -> target[2]='d' (匹配)
总成本 = 1。
但如果考虑另一种情况，例如 source = "abc", target = "ac", insertCost = 5, deleteCost = 3。
方案1：删除 'b'（成本3），得到 "ac"。总成本=3。
方案2：删除 'a'（成本3），删除 'b'（成本3），删除 'c'（成本3），然后插入 'a'（成本5），插入 'c'（成本5），总成本远大于3。显然方案1最优。
但问题描述中只允许插入和删除，不允许替换。因此，这本质上是求两个字符串的“编辑距离”，但只允许插入和删除操作（不允许替换）。
问题分析
这是一个经典的编辑距离问题的变种，通常用动态规划解决。但由于我们只允许插入和删除，状态转移会略有不同。我们定义 dp[i][j] 为将 source 的前 i 个字符转换为 target 的前 j 个字符所需的最小成本。
状态定义
设 dp[i][j] 表示将 source 的前 i 个字符（即 source[0..i-1]）转换为 target 的前 j 个字符（即 target[0..j-1]）的最小成本。
i范围：0 到 n。j范围：0 到 m。
初始状态
dp[0][0] = 0：两个空字符串之间转换不需要任何操作。- 第一行
dp[0][j]：将空字符串转换为target的前j个字符，只能进行j次插入操作，所以dp[0][j] = j * insertCost。 - 第一列
dp[i][0]：将source的前i个字符转换为空字符串，只能进行i次删除操作，所以dp[i][0] = i * deleteCost。
状态转移方程
考虑 dp[i][j] 如何从之前的状态转移而来。我们关注最后一个字符：
-
如果
source[i-1] == target[j-1]，那么最后一个字符已经匹配，不需要额外操作，直接从前面的状态转移：dp[i][j] = dp[i-1][j-1]。 -
如果
source[i-1] != target[j-1]，我们有三种选择（但实际上只允许插入和删除，不允许直接替换，所以“替换”操作需要用一次删除加一次插入来模拟）：- 删除
source[i-1]：这意味着我们先处理source的前i-1个字符到target的前j个字符，然后删除source[i-1]。成本为dp[i-1][j] + deleteCost。 - 插入
target[j-1]：这意味着我们先处理source的前i个字符到target的前j-1个字符，然后插入target[j-1]。成本为dp[i][j-1] + insertCost。
注意：我们不允许直接替换，所以没有
dp[i-1][j-1] + replaceCost的选项。但如果我们允许替换，这里就会加上替换成本。本题只允许插入和删除，所以不匹配时，要么删除多余的字符，要么插入缺失的字符。因此，对于不匹配的情况，转移方程为：
dp[i][j] = min(dp[i-1][j] + deleteCost, dp[i][j-1] + insertCost)。 - 删除
综合起来：
\[dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } source[i-1] == target[j-1] \\ \min(dp[i-1][j] + deleteCost, dp[i][j-1] + insertCost) & \text{otherwise} \end{cases} \]
计算顺序
由于 dp[i][j] 依赖于 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1]，我们可以按行或按列顺序计算，通常使用双重循环：
- 外层循环
i从 0 到 n。 - 内层循环
j从 0 到 m。
注意初始状态已经定义了 i=0 或 j=0 的情况，所以循环从 i=1 和 j=1 开始。
最终答案
最终答案为 dp[n][m]，即将整个 source 转换为整个 target 的最小成本。
示例演算
以 source = "abc", target = "ac", insertCost = 5, deleteCost = 3 为例。
初始化：
dp[0][0] = 0dp[0][1] = 1 * 5 = 5，dp[0][2] = 2 * 5 = 10dp[1][0] = 1 * 3 = 3，dp[2][0] = 2 * 3 = 6，dp[3][0] = 3 * 3 = 9
计算 dp[1][1]：比较 source[0]='a' 和 target[0]='a'，匹配，所以 dp[1][1] = dp[0][0] = 0。
dp[1][2]：source[0]='a'，target[1]='c'，不匹配。
- 删除 'a'：
dp[0][2] + 3 = 10 + 3 = 13 - 插入 'c'：
dp[1][1] + 5 = 0 + 5 = 5
取 min = 5。
dp[2][1]：source[1]='b'，target[0]='a'，不匹配。
- 删除 'b'：
dp[1][1] + 3 = 0 + 3 = 3 - 插入 'a'：
dp[2][0] + 5 = 6 + 5 = 11
取 min = 3。
dp[2][2]：source[1]='b'，target[1]='c'，不匹配。
- 删除 'b'：
dp[1][2] + 3 = 5 + 3 = 8 - 插入 'c'：
dp[2][1] + 5 = 3 + 5 = 8
取 min = 8。
dp[3][1]：source[2]='c'，target[0]='a'，不匹配。
- 删除 'c'：
dp[2][1] + 3 = 3 + 3 = 6 - 插入 'a'：
dp[3][0] + 5 = 9 + 5 = 14
取 min = 6。
dp[3][2]：source[2]='c'，target[1]='c'，匹配！所以 dp[3][2] = dp[2][1] = 3。
最终 dp[3][2] = 3，即最小成本为 3（删除 'b'）。
时间复杂度与空间复杂度
- 时间复杂度：O(n * m)，因为需要填充一个 (n+1) x (m+1) 的二维 DP 表。
- 空间复杂度：O(n * m) 用于存储 DP 表。可以优化到 O(min(n, m)) 使用滚动数组，但通常题目中 n 和 m 在 500 以内，直接二维数组即可。
总结
这个问题是编辑距离的简化版本，只允许插入和删除操作。通过定义 dp[i][j] 并合理考虑状态转移，我们可以高效地求出最小成本。关键点在于理解：当字符匹配时直接继承前状态；不匹配时，选择删除当前源字符或插入当前目标字符中成本较小的方案。