最长公共子序列的变种：带字符插入/删除/替换代价的最短公共超序列（Shortest Common Supersequence with Custom Costs） 题目描述 给定两个字符串 s1 和 s2 ，以及三个操作的成本： 插入 （Insert）：在超序列中插入一个字符，成本为 ins_cost （固定值或每个字符可能有不同成本，这里假设固定）。 删除 （Delete）：从原字符串中删除一个字符，成本为 del_cost （固定）。 替换 （Replace）：替换一个字符为另一个字符，成本为 rep_cost （固定）。 要求构造一个最短公共超序列（SCS），即一个包含 s1 和 s2 作为子序列的最短字符串，并使得所有操作的总成本最小。注意：超序列需保留原字符串字符的相对顺序。 解题过程 定义状态 设 dp[i][j] 表示构造包含 s1[0:i] 和 s2[0:j] 的最短公共超序列的最小成本。其中 i 和 j 分别表示 s1 和 s2 的前缀长度（从 0 开始）。 初始化边界情况 当 i = 0 且 j = 0 ：超序列为空，成本为 0。即 dp[0][0] = 0 。 当 i = 0 ：超序列就是 s2 的前 j 个字符，需全部插入，成本为 j * ins_cost 。即 dp[0][j] = j * ins_cost 。 当 j = 0 ：超序列是 s1 的前 i 个字符，需全部删除（或理解为超序列直接使用 s1 的字符，但删除操作成本为 del_cost ），成本为 i * del_cost 。即 dp[i][0] = i * del_cost 。 状态转移方程 考虑如何由子问题推导 dp[i][j] ： 情况1 ： s1[i-1] 和 s2[j-1] 相同（即末尾字符匹配）。 直接使用该字符一次，无需替换，成本继承自 dp[i-1][j-1] 。 转移： dp[i][j] = dp[i-1][j-1] + 0 （严格来说，匹配字符本身无额外成本，但需注意操作定义：这里匹配字符可视为“直接使用”，成本为0）。 情况2 ：字符不同。 有三种可能操作： 插入 s2[j-1] ：成本为 ins_cost ，状态从 dp[i][j-1] 转移。 删除 s1[i-1] ：成本为 del_cost ，状态从 dp[i-1][j] 转移。 替换 s1[i-1] 为 s2[j-1] ：成本为 rep_cost ，状态从 dp[i-1][j-1] 转移。 转移： dp[i][j] = min(dp[i][j-1] + ins_cost, dp[i-1][j] + del_cost, dp[i-1][j-1] + rep_cost) 。 注意 ：实际实现中，需统一操作语义。更常见的处理是： 若字符相同： dp[i][j] = dp[i-1][j-1] （直接使用该字符）。 若不同： dp[i][j] = min(dp[i][j-1] + ins_cost, dp[i-1][j] + del_cost) ，替换操作可视为删除后插入的组合，但若 rep_cost < ins_cost + del_cost ，则显式定义替换更优。本问题中替换是独立操作，因此需包含在 min 中。 最终答案 最小成本为 dp[len(s1)][len(s2)] 。 示例验证 设 s1 = "abc" , s2 = "adc" ，成本： ins_cost = 1 , del_cost = 1 , rep_cost = 1 。 dp[1][1] （"a" 和 "a"）：字符相同，成本 0。 dp[2][2] （"ab" 和 "ad"）：字符不同，成本 min(dp[2][1]+1, dp[1][2]+1, dp[1][1]+1) = min(1+1, 1+1, 0+1) = 1 （选择替换 b→d）。 dp[3][3] （"abc" 和 "adc"）：字符相同，成本继承 dp[2][2] = 1 。 最终成本为 1，超序列可为 "adbc" 或 "abdc" 等。 关键点 操作成本需对称处理，避免重复计算。 若替换成本过高，算法可能优先选择删除+插入。 时间复杂度 O(mn)，空间复杂度可优化至 O(min(m,n))。