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

字数 2287 2025-11-10 17:53:55

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

问题描述

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

插入成本：在任意位置插入一个字符的成本（可能因字符不同而异）。
删除成本：删除一个字符的成本（可能因字符不同而异）。
替换成本：将一个字符替换为另一个字符的成本（可能因字符不同而异）。

要求找到一个字符串 S，使得 s1 和 s2 都是 S 的子序列，且构造 S 的总成本（即所有插入、删除、替换操作的成本之和）最小。

关键思路

最短公共超序列（SCS） 的标准问题是：找到最短的字符串 S，使得 s1 和 s2 都是其子序列。本题是带成本的扩展。
核心观察：
- 如果 s1[i] == s2[j]，则直接匹配这两个字符（无需额外成本），并继续处理 s1[i+1:] 和 s2[j+1:]。
- 如果 s1[i] != s2[j]，有三种选择：
  - 删除 s1[i]：成本为 delete_cost(s1[i])，然后处理 s1[i+1:] 和 s2[j:]。
  - 插入 s2[j]：成本为 insert_cost(s2[j])，然后处理 s1[i:] 和 s2[j+1:]。
  - 替换 s1[i] 为 s2[j]：成本为 replace_cost(s1[i], s2[j])，然后处理 s1[i+1:] 和 s2[j+1:]。
动态规划定义：
- 设 dp[i][j] 表示将 s1 的前 i 个字符和 s2 的前 j 个字符转化为公共超序列的最小成本。
- 目标：dp[len(s1)][len(s2)]。

状态转移方程

基础情况：
- dp[0][0] = 0（两个空字符串无需操作）。
- dp[i][0] = dp[i-1][0] + delete_cost(s1[i-1])（删除 s1 的所有字符）。
- dp[0][j] = dp[0][j-1] + insert_cost(s2[j-1])（插入 s2 的所有字符）。

一般情况（i > 0, j > 0）：

如果 s1[i-1] == s2[j-1]：
```
dp[i][j] = dp[i-1][j-1]  
```

如果 s1[i-1] != s2[j-1]：

dp[i][j] = min(  
    dp[i-1][j] + delete_cost(s1[i-1]),   // 删除 s1[i-1]  
    dp[i][j-1] + insert_cost(s2[j-1]),   // 插入 s2[j-1]  
    dp[i-1][j-1] + replace_cost(s1[i-1], s2[j-1])  // 替换  
)

详细步骤（以示例说明）

示例：
s1 = "abc", s2 = "adc"
成本：插入/删除任意字符成本为 1，替换成本为 2。

初始化 DP 表（大小为 (4, 4)）：

j=0 j=1 (a) j=2 (d) j=3 (c)

i=0 0 1 2 3

i=1 (a) 1

i=2 (b) 2

i=3 (c) 3
填充表格：
- i=1, j=1：s1[0] = 'a'，s2[0] = 'a'，匹配成功，dp[1][1] = dp[0][0] = 0。
- i=1, j=2：s1[0] = 'a'，s2[1] = 'd'，不匹配：
  - 删除 'a'：dp[0][2] + 1 = 2 + 1 = 3
  - 插入 'd'：dp[1][1] + 1 = 0 + 1 = 1
  - 替换 'a' 为 'd'：dp[0][1] + 2 = 1 + 2 = 3
  - 最小值 = 1 → dp[1][2] = 1
- 继续填充至 i=3, j=3：
  
  j=0 j=1 j=2 j=3
  
  i=0 0 1 2 3
  
  i=1 1 0 1 2
  
  i=2 2 1 2 3
  
  i=3 3 2 3 2
结果：dp[3][3] = 2。
- 解释：最优超序列为 "adbc"（匹配 'a'，插入 'd'，匹配 'c'，删除 'b'？需回溯验证）。
- 实际回溯：
  - (3,3)：'c' 匹配 'c'，回到 (2,2)。
  - (2,2)：'b' 和 'd' 不匹配，选择插入 'd'（成本 1），回到 (2,1)。
  - (2,1)：'b' 和 'a' 不匹配，选择删除 'b'（成本 1），回到 (1,1)。
  - (1,1)：'a' 匹配 'a'，回到 (0,0)。
  - 总成本 = 1 + 1 = 2。

	j=0	j=1 (a)	j=2 (d)	j=3 (c)
i=0	0	1	2	3
i=1 (a)	1
i=2 (b)	2
i=3 (c)	3

	j=0	j=1	j=2	j=3
i=0	0	1	2	3
i=1	1	0	1	2
i=2	2	1	2	3
i=3	3	2	3	2

复杂度分析

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

总结

本题通过动态规划将最短公共超序列问题扩展至带成本操作，关键是在字符不匹配时比较三种操作的成本。实际应用中，成本函数可灵活定制（如基于字符的权重），适用于基因序列对齐、文本差异分析等场景。

线性动态规划：最长公共子序列的变种——带字符插入/删除/替换代价的最短公共超序列（Shortest Common Supersequence with Custom Costs）问题描述给定两个字符串 s1 和 s2 ，以及三个操作的成本：插入成本：在任意位置插入一个字符的成本（可能因字符不同而异）。删除成本：删除一个字符的成本（可能因字符不同而异）。替换成本：将一个字符替换为另一个字符的成本（可能因字符不同而异）。要求找到一个字符串 S ，使得 s1 和 s2 都是 S 的子序列，且构造 S 的总成本（即所有插入、删除、替换操作的成本之和）最小。关键思路最短公共超序列（SCS）的标准问题是：找到最短的字符串 S ，使得 s1 和 s2 都是其子序列。本题是带成本的扩展。核心观察：如果 s1[i] == s2[j] ，则直接匹配这两个字符（无需额外成本），并继续处理 s1[i+1:] 和 s2[j+1:] 。如果 s1[i] != s2[j] ，有三种选择：删除 s1[i] ：成本为 delete_cost(s1[i]) ，然后处理 s1[i+1:] 和 s2[j:] 。插入 s2[j] ：成本为 insert_cost(s2[j]) ，然后处理 s1[i:] 和 s2[j+1:] 。替换 s1[i] 为 s2[j] ：成本为 replace_cost(s1[i], s2[j]) ，然后处理 s1[i+1:] 和 s2[j+1:] 。动态规划定义：设 dp[i][j] 表示将 s1 的前 i 个字符和 s2 的前 j 个字符转化为公共超序列的最小成本。目标： dp[len(s1)][len(s2)] 。状态转移方程基础情况： dp[0][0] = 0 （两个空字符串无需操作）。 dp[i][0] = dp[i-1][0] + delete_cost(s1[i-1]) （删除 s1 的所有字符）。 dp[0][j] = dp[0][j-1] + insert_cost(s2[j-1]) （插入 s2 的所有字符）。一般情况（i > 0, j > 0）：如果 s1[i-1] == s2[j-1] ：如果 s1[i-1] != s2[j-1] ：详细步骤（以示例说明）示例： s1 = "abc" , s2 = "adc" 成本：插入/删除任意字符成本为 1，替换成本为 2。初始化 DP 表（大小为 (4, 4) ）： | | j=0 | j=1 (a) | j=2 (d) | j=3 (c) | |-------|-----|---------|---------|---------| | i=0 | 0 | 1 | 2 | 3 | | i=1 (a)| 1 | | | | | i=2 (b)| 2 | | | | | i=3 (c)| 3 | | | | 填充表格： i=1, j=1 ： s1[0] = 'a' ， s2[0] = 'a' ，匹配成功， dp[1][1] = dp[0][0] = 0 。 i=1, j=2 ： s1[0] = 'a' ， s2[1] = 'd' ，不匹配：删除 'a'： dp[0][2] + 1 = 2 + 1 = 3 插入 'd'： dp[1][1] + 1 = 0 + 1 = 1 替换 'a' 为 'd'： dp[0][1] + 2 = 1 + 2 = 3 最小值 = 1 → dp[1][2] = 1 继续填充至 i=3, j=3 ： | | j=0 | j=1 | j=2 | j=3 | |-------|-----|-----|-----|-----| | i=0 | 0 | 1 | 2 | 3 | | i=1 | 1 | 0 | 1 | 2 | | i=2 | 2 | 1 | 2 | 3 | | i=3 | 3 | 2 | 3 | 2 | 结果： dp[3][3] = 2 。解释：最优超序列为 "adbc" （匹配 'a'，插入 'd'，匹配 'c'，删除 'b'？需回溯验证）。实际回溯： (3,3) ：'c' 匹配 'c'，回到 (2,2) 。 (2,2) ：'b' 和 'd' 不匹配，选择插入 'd'（成本 1），回到 (2,1) 。 (2,1) ：'b' 和 'a' 不匹配，选择删除 'b'（成本 1），回到 (1,1) 。 (1,1) ：'a' 匹配 'a'，回到 (0,0) 。总成本 = 1 + 1 = 2。复杂度分析时间复杂度：O(m·n)，其中 m 和 n 为字符串长度。空间复杂度：O(m·n)，可优化至 O(min(m, n))。总结本题通过动态规划将最短公共超序列问题扩展至带成本操作，关键是在字符不匹配时比较三种操作的成本。实际应用中，成本函数可灵活定制（如基于字符的权重），适用于基因序列对齐、文本差异分析等场景。