最长公共子序列的变种：带字符插入/删除/替换代价的最短公共超序列（Shortest Common Supersequence with Custom Costs）

字数 1686 2025-11-09 03:59:10

最长公共子序列的变种：带字符插入/删除/替换代价的最短公共超序列（Shortest Common Supersequence with Custom Costs）

题目描述
给定两个字符串 s1 和 s2，以及三个操作的成本：

插入一个字符的成本为 insertCost
删除一个字符的成本为 deleteCost
替换一个字符的成本为 replaceCost

目标是找到一个最短公共超序列（SCS），使得该超序列包含 s1 和 s2 作为子序列，且生成该超序列的总操作成本最小。操作允许在任意位置插入、删除或替换字符（替换视为先删除后插入，或直接替换，成本固定为 replaceCost）。

解题过程
步骤1：问题分析
最短公共超序列（SCS）是包含两个字符串作为子序列的最短字符串。经典SCS问题中，操作成本均匀（每个操作成本为1），但本题中操作成本可能不同。我们需要通过动态规划计算最小成本。

关键思路：

若字符匹配，直接保留该字符（成本0）。
若字符不匹配，考虑三种操作：
1. 插入 s2 的字符（成本 insertCost）
2. 删除 s1 的字符（成本 deleteCost）
3. 替换字符（成本 replaceCost）

步骤2：定义状态
设 dp[i][j] 表示将 s1 的前 i 个字符和 s2 的前 j 个字符转化为最短公共超序列的最小成本。

i 的范围：0 ≤ i ≤ len(s1)
j 的范围：0 ≤ j ≤ len(s2)

步骤3：初始状态

dp[0][0] = 0：两个空字符串无需操作。
dp[i][0] = i * deleteCost：删除 s1 的所有字符。
dp[0][j] = j * insertCost：插入 s2 的所有字符。

步骤4：状态转移方程
对每个 (i, j)（i ≥ 1, j ≥ 1）：

字符匹配（s1[i-1] == s2[j-1]）：
- 直接保留字符，成本为0：
  dp[i][j] = dp[i-1][j-1]
字符不匹配（s1[i-1] != s2[j-1]）：
- 插入 s2[j-1]：成本为 dp[i][j-1] + insertCost
- 删除 s1[i-1]：成本为 dp[i-1][j] + deleteCost
- 替换字符：成本为 dp[i-1][j-1] + replaceCost
- 取最小值：
  dp[i][j] = min(dp[i][j-1] + insertCost, dp[i-1][j] + deleteCost, dp[i-1][j-1] + replaceCost)

步骤5：示例计算
设 s1 = "abc", s2 = "adc"，成本：insertCost = 1, deleteCost = 1, replaceCost = 2。

初始化：

dp[0][0] = 0  
dp[1][0] = 1, dp[2][0] = 2, dp[3][0] = 3  
dp[0][1] = 1, dp[0][2] = 2, dp[0][3] = 3

计算 dp[1][1]（s1[0] = 'a', s2[0] = 'a'，匹配）：
dp[1][1] = dp[0][0] = 0

dp[1][2]（s1[0] = 'a', s2[1] = 'd'，不匹配）：

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

最终 dp[3][3] 为最小成本2（超序列为 "adbc"，操作：在 "abc" 中插入 'd'，成本1；或替换 'b' 为 'd' 再插入 'b'，但成本更高）。

步骤6：复杂度分析

时间复杂度：O(mn)，其中 m、n 为字符串长度。
空间复杂度：O(mn)，可优化至 O(min(m,n))。

总结
通过动态规划状态转移，兼顾字符匹配与三种操作的代价，得到最小成本的最短公共超序列。实际超序列可通过回溯 dp 数组生成。

最长公共子序列的变种：带字符插入/删除/替换代价的最短公共超序列（Shortest Common Supersequence with Custom Costs）题目描述给定两个字符串 s1 和 s2 ，以及三个操作的成本：插入一个字符的成本为 insertCost 删除一个字符的成本为 deleteCost 替换一个字符的成本为 replaceCost 目标是找到一个最短公共超序列（SCS），使得该超序列包含 s1 和 s2 作为子序列，且生成该超序列的总操作成本最小。操作允许在任意位置插入、删除或替换字符（替换视为先删除后插入，或直接替换，成本固定为 replaceCost ）。解题过程步骤1：问题分析最短公共超序列（SCS）是包含两个字符串作为子序列的最短字符串。经典SCS问题中，操作成本均匀（每个操作成本为1），但本题中操作成本可能不同。我们需要通过动态规划计算最小成本。关键思路：若字符匹配，直接保留该字符（成本0）。若字符不匹配，考虑三种操作：插入 s2 的字符（成本 insertCost ）删除 s1 的字符（成本 deleteCost ）替换字符（成本 replaceCost ）步骤2：定义状态设 dp[i][j] 表示将 s1 的前 i 个字符和 s2 的前 j 个字符转化为最短公共超序列的最小成本。 i 的范围： 0 ≤ i ≤ len(s1) j 的范围： 0 ≤ j ≤ len(s2) 步骤3：初始状态 dp[0][0] = 0 ：两个空字符串无需操作。 dp[i][0] = i * deleteCost ：删除 s1 的所有字符。 dp[0][j] = j * insertCost ：插入 s2 的所有字符。步骤4：状态转移方程对每个 (i, j) （ i ≥ 1 , j ≥ 1 ）：字符匹配（ s1[i-1] == s2[j-1] ）：直接保留字符，成本为0： dp[i][j] = dp[i-1][j-1] 字符不匹配（ s1[i-1] != s2[j-1] ）：插入 s2[j-1] ：成本为 dp[i][j-1] + insertCost 删除 s1[i-1] ：成本为 dp[i-1][j] + deleteCost 替换字符：成本为 dp[i-1][j-1] + replaceCost 取最小值： dp[i][j] = min(dp[i][j-1] + insertCost, dp[i-1][j] + deleteCost, dp[i-1][j-1] + replaceCost) 步骤5：示例计算设 s1 = "abc", s2 = "adc" ，成本： insertCost = 1, deleteCost = 1, replaceCost = 2 。初始化：计算 dp[1][1] （ s1[0] = 'a' , s2[0] = 'a' ，匹配）： dp[1][1] = dp[0][0] = 0 dp[1][2] （ s1[0] = 'a' , s2[1] = 'd' ，不匹配）：插入： dp[1][1] + 1 = 0 + 1 = 1 删除： dp[0][2] + 1 = 2 + 1 = 3 替换： dp[0][1] + 2 = 1 + 2 = 3 取最小值 1 最终 dp[3][3] 为最小成本2（超序列为 "adbc" ，操作：在 "abc" 中插入 'd' ，成本1；或替换 'b' 为 'd' 再插入 'b' ，但成本更高）。步骤6：复杂度分析时间复杂度：O(mn)，其中 m、n 为字符串长度。空间复杂度：O(mn)，可优化至 O(min(m,n))。总结通过动态规划状态转移，兼顾字符匹配与三种操作的代价，得到最小成本的最短公共超序列。实际超序列可通过回溯 dp 数组生成。