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

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

• 插入一个字符的代价：insert_cost
• 删除一个字符的代价：delete_cost
• 替换一个字符的代价：replace_cost

请计算将word1转换成word2所需的最小总代价。

示例
输入：
word1 = "horse", word2 = "ros"
insert_cost = 1, delete_cost = 1, replace_cost = 1
输出：3
解释：horse -> rorse (替换'h'为'r') -> rose (删除'r') -> ros (删除'e')

解题过程

步骤1：理解问题本质
这是一个经典的动态规划问题，我们需要找到从word1转换到word2的最小代价。每个字符操作都有不同的权重，这比标准的编辑距离问题更通用。

步骤2：定义状态
定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小代价。

步骤3：建立状态转移方程

考虑三种操作：

1. 删除：删除word1的第i个字符，代价为delete_cost
   dp[i][j] = dp[i-1][j] + delete_cost

2. 插入：在word1中插入word2的第j个字符，代价为insert_cost
   dp[i][j] = dp[i][j-1] + insert_cost

3. 替换：

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

综合起来：
dp[i][j] = min(
dp[i-1][j] + delete_cost, # 删除
dp[i][j-1] + insert_cost, # 插入
dp[i-1][j-1] + (0 if word1[i-1]==word2[j-1] else replace_cost) # 替换或匹配
)

步骤4：初始化边界情况

• dp[0][0] = 0 # 空字符串到空字符串
• dp[i][0] = i * delete_cost # word1前i个字符转换为空字符串，全部删除
• dp[0][j] = j * insert_cost # 空字符串转换为word2前j个字符，全部插入

步骤5：计算顺序
按行或按列顺序计算，确保计算dp[i][j]时，dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]都已计算。

步骤6：代码实现

def minDistanceWithCost(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] = i * delete_cost
    for j in range(1, n + 1):
        dp[0][j] = j * insert_cost
    
    # 动态规划计算
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                replace_cost_current = 0
            else:
                replace_cost_current = 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_current # 替换或匹配
            )
    
    return dp[m][n]

步骤7：复杂度分析

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

步骤8：示例验证
以示例"horse"→"ros"为例：

• 删除'h'：代价1
• 替换'r'→'r'：代价0
• 删除'o'：代价1
• 删除's'：代价1
• 删除'e'：代价1
  总代价：4（不是最优）

最优路径：

• 替换'h'→'r'：代价1
• 删除'r'：代价1
• 删除'e'：代价1
  总代价：3

通过动态规划表格计算可以验证这个结果。