线性动态规划：最长公共子序列的变种——带字符插入/删除/替换代价的最短编辑距离（Edit Distance with Custom Costs）

题目描述
给定两个字符串 word1 和 word2，以及三个整数 insertCost、deleteCost 和 replaceCost，分别表示插入一个字符、删除一个字符和替换一个字符的代价。要求计算将 word1 转换成 word2 所需的最小总代价。注意，替换操作的代价仅在两个字符不同时发生；若字符相同，替换代价为0。

解题过程

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

   • 初始状态：dp[0][0] = 0（两个空字符串无需操作）。
   • 边界情况：
     • 若 word1 为空，需将 word2 的 j 个字符全部插入：dp[0][j] = j * insertCost。
     • 若 word2 为空，需删除 word1 的 i 个字符：dp[i][0] = i * deleteCost。

2. 状态转移方程
   对于每个位置 (i, j)，考虑三种操作：

   • 插入：在 word1 的前 i 个字符后插入 word2 的第 j 个字符，代价为 dp[i][j-1] + insertCost。
   • 删除：删除 word1 的第 i 个字符，代价为 dp[i-1][j] + deleteCost。
   • 替换/匹配：
     • 若 word1[i-1] == word2[j-1]，直接匹配，代价为 dp[i-1][j-1]（无需替换）。
     • 否则，替换 word1[i-1] 为 word2[j-1]，代价为 dp[i-1][j-1] + replaceCost。
       综合上述情况，状态转移方程为：

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

3. 计算顺序
   按 i 从 0 到 len(word1)，j 从 0 到 len(word2) 的顺序填充 dp 表，确保计算 dp[i][j] 时所需的前置状态已就绪。

4. 举例说明
   设 word1 = "abc", word2 = "adc"，代价为 insertCost = 1, deleteCost = 1, replaceCost = 2。

   • 初始化：dp[0][0] = 0，dp[0][1..3] = [1, 2, 3]，dp[1..3][0] = [1, 2, 3]。
   • 计算 dp[1][1]（比较 "a" 和 "a"）：
     • 插入：dp[1][0] + 1 = 1 + 1 = 2
     • 删除：dp[0][1] + 1 = 1 + 1 = 2
     • 匹配：dp[0][0] + 0 = 0
     • 结果：dp[1][1] = 0
   • 计算 dp[2][2]（比较 "ab" 和 "ad"）：
     • 插入：dp[2][1] + 1 = 2 + 1 = 3
     • 删除：dp[1][2] + 1 = 2 + 1 = 3
     • 替换：dp[1][1] + 2 = 0 + 2 = 2
     • 结果：dp[2][2] = 2
   • 最终 dp[3][3] = 2（将 "b" 替换为 "d"，代价为2）。

5. 复杂度分析
   时间复杂度：O(mn)，空间复杂度：O(mn)（可优化至 O(min(m, n))）。

总结
通过动态规划将问题分解为子问题，逐步考虑每种操作的代价，最终得到最小编辑代价。此方法适用于自定义代价的编辑场景，如文本纠错或基因序列比对。