合并字符串的最小成本问题（字符插入、删除、替换）

题目描述
给定两个字符串word1和word2，以及三个整数：插入成本insertCost、删除成本deleteCost、替换成本replaceCost。你可以对word1执行以下三种操作，每次操作都需要消耗对应成本：

1. 插入一个字符（成本为insertCost）
2. 删除一个字符（成本为deleteCost）
3. 替换一个字符（成本为replaceCost）

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

解题过程

1. 问题分析
这是一个经典的编辑距离问题的扩展版本，不同之处在于每个操作的成本可以自定义。我们需要找到将word1转换为word2的最小成本操作序列。

2. 状态定义
定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小成本。

3. 状态转移方程

考虑三种操作对状态的影响：

• 删除操作：删除word1的第i个字符，然后考虑将前i-1个字符转换为前j个字符
  dp[i][j] = dp[i-1][j] + deleteCost

• 插入操作：在word1的第i个位置后插入一个字符，然后考虑将前i个字符转换为前j-1个字符
  dp[i][j] = dp[i][j-1] + insertCost

• 替换操作：

  • 如果word1[i-1] == word2[j-1]：字符相同，不需要替换
    dp[i][j] = dp[i-1][j-1]
  • 如果字符不同：需要替换操作
    dp[i][j] = dp[i-1][j-1] + replaceCost

4. 边界条件初始化

• dp[0][0] = 0：两个空字符串的转换成本为0
• dp[i][0] = i * deleteCost：将前i个字符转换为空字符串，需要删除所有字符
• dp[0][j] = j * insertCost：将空字符串转换为前j个字符，需要插入所有字符

5. 完整算法步骤

def minDistance(word1, word2, insertCost, deleteCost, replaceCost):
    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 * deleteCost
    for j in range(1, n + 1):
        dp[0][j] = j * insertCost
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                # 字符相同，不需要替换
                dp[i][j] = dp[i-1][j-1]
            else:
                # 字符不同，考虑替换
                dp[i][j] = dp[i-1][j-1] + replaceCost
            
            # 考虑删除和插入操作
            dp[i][j] = min(dp[i][j], 
                          dp[i-1][j] + deleteCost,  # 删除word1[i-1]
                          dp[i][j-1] + insertCost)   # 插入word2[j-1]
    
    return dp[m][n]

6. 示例演示

假设word1 = "horse", word2 = "ros"，成本：insertCost=1, deleteCost=1, replaceCost=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[5][3] = 3

7. 复杂度分析

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

8. 特殊情况处理

• 如果某个成本为0，对应操作变为免费
• 如果replaceCost > insertCost + deleteCost，替换操作不如先删除再插入
• 空字符串到空字符串的成本为0