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

题目描述
给定两个字符串 s1 和 s2，以及三个操作的成本：插入一个字符的成本 insert_cost、删除一个字符的成本 delete_cost、替换一个字符的成本 replace_cost。目标是找到包含 s1 和 s2 作为子序列的最短字符串（即最短公共超序列），并使得构造该超序列的总操作成本最小。操作允许在任意位置插入、删除或替换字符，且每次操作的成本固定。

解题过程

1. 问题分析

   • 最短公共超序列（SCS）是包含两个字符串作为子序列的最短字符串。
   • 本题中，操作成本可能不对称（例如插入和删除成本不同），需通过动态规划计算最小成本。
   • 关键点：超序列的生成可视为对 s1 和 s2 的编辑过程，通过插入、删除、替换操作使两字符串对齐。

2. 状态定义

   • 定义 dp[i][j] 表示将 s1 的前 i 个字符和 s2 的前 j 个字符转化为超序列的最小成本。
   • 初始状态：
     • dp[0][0] = 0（两个空字符串无需操作）。
     • dp[i][0] = i * delete_cost（删除 s1 的前 i 个字符）。
     • dp[0][j] = j * insert_cost（将 s2 的前 j 个字符插入到空字符串）。

3. 状态转移方程

   • 对于 s1[i-1] 和 s2[j-1]：
     • 若 s1[i-1] == s2[j-1]：直接匹配，无需额外成本，dp[i][j] = dp[i-1][j-1]。
     • 若字符不相等，考虑三种操作：
       1. 删除 s1[i-1]：成本为 delete_cost，状态转移为 dp[i][j] = dp[i-1][j] + delete_cost。
       2. 插入 s2[j-1]：成本为 insert_cost，状态转移为 dp[i][j] = dp[i][j-1] + insert_cost。
       3. 替换 s1[i-1] 为 s2[j-1]：成本为 replace_cost，状态转移为 dp[i][j] = dp[i-1][j-1] + replace_cost。
   • 最终 dp[i][j] 取上述情况的最小值：

     dp[i][j] = min(
         dp[i-1][j] + delete_cost,
         dp[i][j-1] + insert_cost,
         dp[i-1][j-1] + (0 if s1[i-1] == s2[j-1] else replace_cost)
     )
     

4. 示例计算
   设 s1 = "abc", s2 = "adc"，成本为 insert_cost = 1, delete_cost = 1, replace_cost = 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'，取最小值：
     • 删除 '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。
   • 最终 dp[3][3] = 2（超序列为 "adbc"，成本：插入 'd' 成本 1，匹配 'b' 和 'c' 无成本）。

5. 复杂度分析

   • 时间复杂度：O(mn)，其中 m 和 n 为两字符串长度。
   • 空间复杂度：可优化至 O(min(m, n))，通过滚动数组存储状态。

总结
本题通过动态规划将字符匹配问题转化为成本最小化问题，状态转移需综合考虑插入、删除、替换操作的代价差异，最终得到最小成本超序列。