线性动态规划：最长公共子序列的变种——带字符插入/删除代价的最短公共超序列（Shortest Common Supersequence with Custom Costs）
字数 2125 2025-11-08 20:56:05

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

题目描述
给定两个字符串 s1 和 s2，以及两个整数 cost_ins 和 cost_del，分别表示插入一个字符和删除一个字符的代价。目标是找到一个字符串 S，使得 s1 和 s2 都是 S 的子序列，并且构造 S 的总代价最小。构造代价定义为：

  • 如果 S 中的某个字符来自 s1 或 s2 的原有字符，则无代价。
  • 如果需要在 S 中插入一个不在 s1 或 s2 中的字符（为了匹配另一个字符串的字符），代价为 cost_ins。
  • 如果需要删除 s1 或 s2 中的某个字符（即不将其纳入 S），代价为 cost_del。

示例
输入：

s1 = "abc", s2 = "adc", cost_ins = 1, cost_del = 1

输出：
最小代价为 0，因为最短公共超序列可以是 "adbc"（s1 和 s2 都是其子序列，无需额外操作）。
但若 s1 = "abc", s2 = "ac", cost_ins = 2, cost_del = 3，则最小代价为 3（删除 s1 中的 'b'，代价 3）。

解题过程

步骤 1：问题分析

  • 最短公共超序列（SCS）是包含两个字符串作为子序列的最短字符串。
  • 本题中，允许通过插入（代价 cost_ins）或删除（代价 cost_del）字符来调整字符串，目标是最小化总代价。
  • 关键观察：如果 s1 和 s2 的某个字符匹配，则可以免费纳入超序列；如果不匹配，则需要选择删除 s1 的字符或删除 s2 的字符（等价于在另一个字符串中插入字符）。

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

  • i 范围：0 到 len(s1)
  • j 范围：0 到 len(s2)

步骤 3：状态转移方程
考虑如何从子问题推导 dp[i][j]：

  1. 如果 s1[i-1] == s2[j-1]（字符匹配）：
    • 直接将该字符纳入超序列，无额外代价。
    • dp[i][j] = dp[i-1][j-1]
  2. 如果字符不匹配：
    • 选择删除 s1[i-1]（或等价于在 s2 中插入该字符）：代价为 cost_del，状态转为 dp[i-1][j]。
    • 选择删除 s2[j-1]（或等价于在 s1 中插入该字符）：代价为 cost_ins，状态转为 dp[i][j-1]。
    • 取最小代价：
      dp[i][j] = min(dp[i-1][j] + cost_del, dp[i][j-1] + cost_ins)

步骤 4：初始化边界

  • dp[0][0] = 0：两个空字符串无需操作。
  • dp[i][0]：将 s1 的前 i 个字符全部删除（代价 i * cost_del）。
  • dp[0][j]：将 s2 的前 j 个字符全部删除（代价 j * cost_ins，因为删除 s2 的字符等价于在 s1 中插入）。

步骤 5：计算顺序
按 i 从 0 到 len(s1)，j 从 0 到 len(s2) 顺序计算。

步骤 6：示例演算
以 s1 = "abc", s2 = "ac", cost_ins = 2, cost_del = 3 为例：
初始化：

dp[0][0] = 0  
dp[1][0] = 1*3 = 3, dp[2][0] = 6, dp[3][0] = 9  
dp[0][1] = 1*2 = 2, dp[0][2] = 4

计算 dp[1][1]：

  • s1[0] = 'a', s2[0] = 'a'，匹配 → dp[1][1] = dp[0][0] = 0

dp[1][2]：

  • s1[0] = 'a', s2[1] = 'c'，不匹配
  • 选项1：删除 'a'（代价 3）→ dp[0][2] + 3 = 4 + 3 = 7
  • 选项2：删除 'c'（代价 2）→ dp[1][1] + 2 = 0 + 2 = 2
  • 取最小值 2

dp[2][1]：

  • s1[1] = 'b', s2[0] = 'a'，不匹配
  • 删除 'b'（代价 3）→ dp[1][1] + 3 = 0 + 3 = 3
  • 删除 'a'（代价 2）→ dp[2][0] + 2 = 6 + 2 = 8
  • 取最小值 3

dp[2][2]：

  • s1[1] = 'b', s2[1] = 'c'，不匹配
  • 删除 'b' → dp[1][2] + 3 = 2 + 3 = 5
  • 删除 'c' → dp[2][1] + 2 = 3 + 2 = 5
  • 取最小值 5

dp[3][2]：

  • s1[2] = 'c', s2[1] = 'c'，匹配 → dp[2][1] = 3
    最终结果：dp[3][2] = 3。

步骤 7：复杂度分析

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

通过以上步骤，我们得到了带自定义插入/删除代价的最短公共超序列的最小代价。

线性动态规划：最长公共子序列的变种——带字符插入/删除代价的最短公共超序列（Shortest Common Supersequence with Custom Costs） 题目描述 给定两个字符串 s1 和 s2 ，以及两个整数 cost_ins 和 cost_del ，分别表示插入一个字符和删除一个字符的代价。目标是找到一个字符串 S ，使得 s1 和 s2 都是 S 的子序列，并且构造 S 的总代价最小。构造代价定义为： 如果 S 中的某个字符来自 s1 或 s2 的原有字符，则无代价。 如果需要在 S 中插入一个不在 s1 或 s2 中的字符（为了匹配另一个字符串的字符），代价为 cost_ins 。 如果需要删除 s1 或 s2 中的某个字符（即不将其纳入 S ），代价为 cost_del 。 示例 输入： 输出： 最小代价为 0，因为最短公共超序列可以是 "adbc"（s1 和 s2 都是其子序列，无需额外操作）。 但若 s1 = "abc", s2 = "ac", cost_ins = 2, cost_del = 3 ，则最小代价为 3（删除 s1 中的 'b'，代价 3）。 解题过程 步骤 1：问题分析 最短公共超序列（SCS）是包含两个字符串作为子序列的最短字符串。 本题中，允许通过插入（代价 cost_ins ）或删除（代价 cost_del ）字符来调整字符串，目标是最小化总代价。 关键观察：如果 s1 和 s2 的某个字符匹配，则可以免费纳入超序列；如果不匹配，则需要选择删除 s1 的字符或删除 s2 的字符（等价于在另一个字符串中插入字符）。 步骤 2：定义状态 设 dp[i][j] 表示将 s1 的前 i 个字符和 s2 的前 j 个字符转化为公共超序列的最小代价。 i 范围：0 到 len(s1) j 范围：0 到 len(s2) 步骤 3：状态转移方程 考虑如何从子问题推导 dp[i][j] ： 如果 s1[i-1] == s2[j-1] （字符匹配）： 直接将该字符纳入超序列，无额外代价。 dp[i][j] = dp[i-1][j-1] 如果字符不匹配 ： 选择删除 s1[i-1] （或等价于在 s2 中插入该字符）：代价为 cost_del ，状态转为 dp[i-1][j] 。 选择删除 s2[j-1] （或等价于在 s1 中插入该字符）：代价为 cost_ins ，状态转为 dp[i][j-1] 。 取最小代价： dp[i][j] = min(dp[i-1][j] + cost_del, dp[i][j-1] + cost_ins) 步骤 4：初始化边界 dp[0][0] = 0 ：两个空字符串无需操作。 dp[i][0] ：将 s1 的前 i 个字符全部删除（代价 i * cost_del ）。 dp[0][j] ：将 s2 的前 j 个字符全部删除（代价 j * cost_ins ，因为删除 s2 的字符等价于在 s1 中插入）。 步骤 5：计算顺序 按 i 从 0 到 len(s1) ， j 从 0 到 len(s2) 顺序计算。 步骤 6：示例演算 以 s1 = "abc", s2 = "ac", cost_ins = 2, cost_del = 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] = 'c' ，不匹配 选项1：删除 'a'（代价 3）→ dp[0][2] + 3 = 4 + 3 = 7 选项2：删除 'c'（代价 2）→ dp[1][1] + 2 = 0 + 2 = 2 取最小值 2 dp[2][1] ： s1[1] = 'b' , s2[0] = 'a' ，不匹配 删除 'b'（代价 3）→ dp[1][1] + 3 = 0 + 3 = 3 删除 'a'（代价 2）→ dp[2][0] + 2 = 6 + 2 = 8 取最小值 3 dp[2][2] ： s1[1] = 'b' , s2[1] = 'c' ，不匹配 删除 'b' → dp[1][2] + 3 = 2 + 3 = 5 删除 'c' → dp[2][1] + 2 = 3 + 2 = 5 取最小值 5 dp[3][2] ： s1[2] = 'c' , s2[1] = 'c' ，匹配 → dp[2][1] = 3 最终结果： dp[3][2] = 3 。 步骤 7：复杂度分析 时间复杂度：O(mn)，其中 m、n 为字符串长度。 空间复杂度：可优化至 O(min(m, n))。 通过以上步骤，我们得到了带自定义插入/删除代价的最短公共超序列的最小代价。