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

我将为您详细讲解这个线性动态规划问题。这个问题是经典最短公共超序列（SCS）问题的扩展版本，增加了字符操作的代价权重。

问题描述
给定两个字符串s和t，以及三个操作函数：

• 插入代价：ins(c) - 在超序列中插入字符c的代价
• 删除代价：del(c) - 从原字符串中删除字符c的代价
• 替换代价：rep(c1, c2) - 将字符c1替换为c2的代价

我们需要找到一个最短公共超序列，使得该序列同时包含s和t作为子序列，并且所有操作的总代价最小。

解题思路
我们使用动态规划来解决这个问题。定义dp[i][j]表示将s的前i个字符和t的前j个字符转换为最短公共超序列的最小代价。

详细解题步骤

步骤1：定义状态
设dp[i][j]表示处理s的前i个字符和t的前j个字符所需的最小代价。

步骤2：初始化基础情况

• dp[0][0] = 0（两个空字符串不需要任何操作）
• 对于i从1到m：dp[i][0] = dp[i-1][0] + del(s[i-1])（删除s的所有字符）
• 对于j从1到n：dp[0][j] = dp[0][j-1] + ins(t[j-1])（插入t的所有字符）

步骤3：状态转移方程
对于每个位置(i, j)，考虑三种情况：

1. 删除s[i-1]：
   dp[i][j] = min(dp[i][j], dp[i-1][j] + del(s[i-1]))

2. 插入t[j-1]：
   dp[i][j] = min(dp[i][j], dp[i][j-1] + ins(t[j-1]))

3. 匹配或替换：

   • 如果s[i-1] == t[j-1]：直接匹配，无额外代价
     dp[i][j] = min(dp[i][j], dp[i-1][j-1])
   • 如果s[i-1] ≠ t[j-1]：需要替换操作
     dp[i][j] = min(dp[i][j], dp[i-1][j-1] + rep(s[i-1], t[j-1]))

步骤4：完整算法实现

def shortest_common_supersequence_with_costs(s, t, ins_cost, del_cost, rep_cost):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] + del_cost(s[i-1])
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] + ins_cost(t[j-1])
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # 情况1：删除s[i-1]
            option1 = dp[i-1][j] + del_cost(s[i-1])
            
            # 情况2：插入t[j-1]
            option2 = dp[i][j-1] + ins_cost(t[j-1])
            
            # 情况3：匹配或替换
            if s[i-1] == t[j-1]:
                option3 = dp[i-1][j-1]
            else:
                option3 = dp[i-1][j-1] + rep_cost(s[i-1], t[j-1])
            
            dp[i][j] = min(option1, option2, option3)
    
    return dp[m][n]

步骤5：具体示例
假设：

• s = "ABC", t = "ADC"
• ins_cost(c) = 1（所有字符插入代价为1）
• del_cost(c) = 1（所有字符删除代价为1）
• rep_cost(c1, c2) = 1 if c1 ≠ c2 else 0（不同字符替换代价为1）

计算过程：

初始化：
dp[0][0] = 0
dp[1][0] = 1 (删除A)
dp[2][0] = 2 (删除A,B)
dp[3][0] = 3 (删除A,B,C)
dp[0][1] = 1 (插入A)
dp[0][2] = 2 (插入A,D)
dp[0][3] = 3 (插入A,D,C)

填充表格：
dp[1][1]: s[0]='A', t[0]='A' → 匹配，dp[0][0]=0
dp[1][2]: min(删除A:1+1=2, 插入D:0+1=1, 替换:0+1=1) = 1
dp[1][3]: min(删除A:2+1=3, 插入C:1+1=2, 替换:1+1=2) = 2
...
最终结果：dp[3][3] = 1

步骤6：重构超序列
要重构实际的超序列，我们需要记录每一步的选择：

def reconstruct_supersequence(s, t, dp, ins_cost, del_cost, rep_cost):
    i, j = len(s), len(t)
    result = []
    
    while i > 0 or j > 0:
        if i > 0 and dp[i][j] == dp[i-1][j] + del_cost(s[i-1]):
            # 选择了删除操作
            i -= 1
        elif j > 0 and dp[i][j] == dp[i][j-1] + ins_cost(t[j-1]):
            # 选择了插入操作
            result.append(t[j-1])
            j -= 1
        else:
            # 选择了匹配或替换
            if i > 0 and j > 0:
                if s[i-1] == t[j-1]:
                    result.append(s[i-1])
                else:
                    result.append(t[j-1])  # 替换后的字符
                i -= 1
                j -= 1
    
    return ''.join(reversed(result))

步骤7：复杂度分析

• 时间复杂度：O(m×n)，其中m和n分别是字符串s和t的长度
• 空间复杂度：O(m×n)，可以优化到O(min(m,n))

这个算法通过动态规划系统地考虑了所有可能的操作组合，确保找到代价最小的最短公共超序列。