编辑距离问题（带权重版本）

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

• 插入一个字符的成本为 insertCost
• 删除一个字符的成本为 deleteCost
• 替换一个字符的成本为 replaceCost（若两字符相同，替换成本为0）

求将 word1 转换成 word2 所需的最小总成本。

示例
输入：

word1 = "horse"  
word2 = "ros"  
insertCost = 1, deleteCost = 1, replaceCost = 1  

输出：3（解释：horse → rorse（替换h→r，成本1）→ rose（删除r，成本1）→ ros（删除e，成本1））

解题过程

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

• i 的范围是 0 到 len(word1)，j 的范围是 0 到 len(word2)。
• 当 i=0 时，表示 word1 为空，需插入 j 个字符；当 j=0 时，表示 word2 为空，需删除 i 个字符。

2. 初始化边界

• dp[0][0] = 0（空字符串转空字符串成本为0）
• dp[i][0] = i * deleteCost（删除 word1 的前 i 个字符）
• dp[0][j] = j * insertCost（插入 word2 的前 j 个字符）

3. 状态转移方程
对于每个 i > 0 和 j > 0，考虑对 word1[i-1] 和 word2[j-1] 的操作：

1. 删除 word1[i-1]：成本为 dp[i-1][j] + deleteCost
2. 插入 word2[j-1]：成本为 dp[i][j-1] + insertCost
3. 替换/匹配：
   • 若 word1[i-1] == word2[j-1]，直接匹配，成本为 dp[i-1][j-1]
   • 否则，替换成本为 dp[i-1][j-1] + replaceCost

转移方程：

dp[i][j] = min(  
    dp[i-1][j] + deleteCost,  
    dp[i][j-1] + insertCost,  
    dp[i-1][j-1] + (0 if word1[i-1] == word2[j-1] else replaceCost)  
)  

4. 计算顺序
按 i 从 0 到 len(word1)，j 从 0 到 len(word2) 顺序计算，确保子问题已解决。

5. 最终答案
dp[len(word1)][len(word2)] 即为最小成本。

详细示例演算
以 word1="horse", word2="ros" 为例（成本均为1）：

初始化：

dp[0][0]=0, dp[1][0]=1, dp[2][0]=2, ...  
dp[0][1]=1, dp[0][2]=2, dp[0][3]=3  

计算 dp[1][1]（"h"→"r"）：

• 删除"h"：dp[0][1] + 1 = 1 + 1 = 2
• 插入"r"：dp[1][0] + 1 = 1 + 1 = 2
• 替换"h"为"r"：dp[0][0] + 1 = 0 + 1 = 1
  取最小值 1

继续填表，最终 dp[5][3] = 3，与示例一致。

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：可优化至 O(min(m,n))