编辑距离（Edit Distance）的变种——带权编辑距离

我将为您详细讲解带权编辑距离这个线性动态规划问题。这是一个经典的字符串处理问题，在自然语言处理、生物信息学等领域有广泛应用。

问题描述
给定两个字符串word1和word2，以及三种编辑操作的权重：

• 插入操作权重：insert_cost
• 删除操作权重：delete_cost
• 替换操作权重：replace_cost

要求计算将word1转换为word2所需的最小总权重（即最小编辑代价）。

解题思路
我们使用动态规划来解决这个问题。定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小编辑代价。

详细解题步骤

步骤1：定义状态

• dp[i][j]：将word1[0:i]转换为word2[0:j]的最小编辑代价
• i的范围：0到len(word1)
• j的范围：0到len(word2)

步骤2：初始化基础情况

1. 空字符串转换为空字符串：dp[0][0] = 0
2. 空字符串转换为非空字符串：只能通过插入操作
   dp[0][j] = dp[0][j-1] + insert_cost
3. 非空字符串转换为空字符串：只能通过删除操作
   dp[i][0] = dp[i-1][0] + delete_cost

步骤3：状态转移方程
对于每个位置(i, j)，考虑三种可能的操作：

1. 删除操作：删除word1的第i个字符
   cost_delete = dp[i-1][j] + delete_cost

2. 插入操作：在word1中插入word2的第j个字符
   cost_insert = dp[i][j-1] + insert_cost

3. 替换操作：

   • 如果word1[i-1] == word2[j-1]，不需要替换，代价为0
   • 如果字符不同，需要替换，代价为replace_cost
     cost_replace = dp[i-1][j-1] + (0 if word1[i-1] == word2[j-1] else replace_cost)

状态转移方程：
dp[i][j] = min(cost_delete, cost_insert, cost_replace)

步骤4：计算顺序
我们按行优先的顺序计算dp数组，从i=0到len(word1)，j=0到len(word2)

步骤5：最终结果
dp[len(word1)][len(word2)]就是最小编辑代价

具体示例
假设：
word1 = "horse", word2 = "ros"
insert_cost = 1, delete_cost = 1, replace_cost = 1

构建dp表：

     ''  r   o   s
''   0   1   2   3
h    1   1   2   3
o    2   2   1   2
r    3   2   2   2
s    4   3   3   2
e    5   4   4   3

计算过程：

• dp[0][0] = 0
• dp[0][1] = dp[0][0] + 1 = 1 (插入'r')
• dp[1][0] = dp[0][0] + 1 = 1 (删除'h')
• dp[1][1] = min(
  dp[0][1] + 1 = 2, // 删除'h'
  dp[1][0] + 1 = 2, // 插入'r'
  dp[0][0] + 1 = 1 // 替换'h'为'r'
  ) = 1

最终结果：dp[5][3] = 3

步骤6：算法实现

def weighted_edit_distance(word1, word2, insert_cost, delete_cost, replace_cost):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化
    for i in range(1, m + 1):
        dp[i][0] = dp[i-1][0] + delete_cost
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j-1] + insert_cost
    
    # 填充dp表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                replace_cost_curr = 0
            else:
                replace_cost_curr = replace_cost
                
            dp[i][j] = min(
                dp[i-1][j] + delete_cost,      # 删除
                dp[i][j-1] + insert_cost,      # 插入
                dp[i-1][j-1] + replace_cost_curr  # 替换或匹配
            )
    
    return dp[m][n]

步骤7：复杂度分析

• 时间复杂度：O(m×n)，其中m和n分别是两个字符串的长度
• 空间复杂度：O(m×n)，可以使用滚动数组优化到O(min(m,n))

这个算法可以灵活处理不同权重的编辑操作，在实际应用中可以根据具体需求调整各种操作的代价。