最长公共子序列的变种：带字符插入/删除/替换代价的最短编辑距离（Edit Distance with Custom Costs）
题目描述
给定两个字符串 word1 和 word2，现在定义三种操作：
- 插入一个字符，操作代价为
c_ins（固定值）； - 删除一个字符，操作代价为
c_del（固定值）； - 替换一个字符，操作代价为
c_rep（固定值），只有当字符不同时才需要替换。
要求计算从 word1 变成 word2 所需的最小总代价。
示例
输入：
word1 = "horse", word2 = "ros"
c_ins = 1, c_del = 1, c_rep = 1
输出：3
解释：
horse → rorse (替换 'h' 为 'r'，代价1)
rorse → rose (删除 'r'（第二个r），代价1)
rose → ros (删除 'e'，代价1)
总代价 = 3
问题分析
这是一个经典的编辑距离问题，但扩展为可自定义三种操作的代价。
设：
m = len(word1)n = len(word2)
定义 dp[i][j] 为：将 word1[0..i-1] 变为 word2[0..j-1] 的最小操作代价。
- 注意：
i和j指的是前 i 个和前 j 个字符（1-based 索引更方便，0表示空串）。
状态转移方程推导
1. 边界情况
- 如果
i = 0且j = 0：两个空串，无需操作，dp[0][0] = 0。 - 如果
i = 0且j > 0：需要插入 j 个字符，代价 =j * c_ins。 - 如果
i > 0且j = 0：需要删除 i 个字符，代价 =i * c_del。
2. 一般情况
对 dp[i][j]，有四种可能（实际三种情况）：
-
从
dp[i-1][j]转移：
先让word1[0..i-2]变成word2[0..j-1]，然后再删除word1[i-1]。
总代价 =dp[i-1][j] + c_del。 -
从
dp[i][j-1]转移：
先让word1[0..i-1]变成word2[0..j-2]，然后再插入word2[j-1]。
总代价 =dp[i][j-1] + c_ins。 -
从
dp[i-1][j-1]转移：
先让word1[0..i-2]变成word2[0..j-2]，再处理最后一个字符：- 如果
word1[i-1] == word2[j-1]，则不需要替换，代价 =dp[i-1][j-1]。 - 如果不同，则需要替换，代价 =
dp[i-1][j-1] + c_rep。
- 如果
综上：
if word1[i-1] == word2[j-1]:
replace_cost = 0
else:
replace_cost = c_rep
dp[i][j] = min(
dp[i-1][j] + c_del, # 删除
dp[i][j-1] + c_ins, # 插入
dp[i-1][j-1] + replace_cost # 替换或匹配
)
逐步计算示例
word1 = "horse", word2 = "ros"
c_ins = 1, c_del = 1, c_rep = 1
初始化 dp 表格（m=5, n=3）：
先填写边界：
dp[0][j] = j * 1
dp[i][0] = i * 1
| "" | r | o | s | |
|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 |
| h | 1 | |||
| o | 2 | |||
| r | 3 | |||
| s | 4 | |||
| e | 5 |
计算 dp[1][1]（h → r）
删除：dp[0][1] + 1 = 1 + 1 = 2
插入：dp[1][0] + 1 = 1 + 1 = 2
替换：dp[0][0] + 1 = 0 + 1 = 1（h≠r）
min = 1，填入：
| "" | r | o | s | |
|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 |
| h | 1 | 1 |
计算 dp[1][2]（h → o）
删除：dp[0][2] + 1 = 2 + 1 = 3
插入：dp[1][1] + 1 = 1 + 1 = 2
替换：dp[0][1] + 1 = 1 + 1 = 2（h≠o）
min = 2，填入：
| "" | r | o | s | |
|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 |
计算 dp[1][3]（h → s）
删除：dp[0][3] + 1 = 3 + 1 = 4
插入：dp[1][2] + 1 = 2 + 1 = 3
替换：dp[0][2] + 1 = 2 + 1 = 3（h≠s）
min = 3，填入。
继续按行填完：
dp[2][1]（o → r）：
删除：dp[1][1] + 1 = 1 + 1 = 2
插入：dp[2][0] + 1 = 2 + 1 = 3
替换：dp[1][0] + 1 = 1 + 1 = 2（o≠r）
min = 2
dp[2][2]（o → o）：
删除：dp[1][2] + 1 = 2 + 1 = 3
插入：dp[2][1] + 1 = 2 + 1 = 3
替换：dp[1][1] + 0 = 1 + 0 = 1（相同）
min = 1
dp[2][3]（o → s）：
删除：dp[1][3] + 1 = 3 + 1 = 4
插入：dp[2][2] + 1 = 1 + 1 = 2
替换：dp[1][2] + 1 = 2 + 1 = 3（o≠s）
min = 2
依此类推，最终得到：
完整 dp 表（部分关键值）：
dp[3][1]（r → r）= min(dp[2][0]+1=3, dp[3][0]+1=4, dp[2][0]+0=2) = 2
...
最后 dp[5][3] = 3
时间复杂度与空间优化
时间复杂度：O(m × n)
空间复杂度：可优化为 O(n) 或 O(m)，只保留前一行的 dp 值。
因为 dp[i][j] 只依赖 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]。
用两个一维数组（一个保存上一行，一个当前行）即可。
关键点总结
- 状态定义要清晰：dp[i][j] 表示从 word1 前 i 个字符到 word2 前 j 个字符的最小代价。
- 三种操作对应三个方向的转移：
- 删除：从左边来
- 插入：从上边来
- 替换/匹配：从左上角来
- 如果替换代价小于删除+插入代价之和，才可能用替换；否则可能用删除+插入代替替换，但本例通常 c_rep 不一定小于 c_del + c_ins，所以比较时要完整比较三种情况。
- 当 c_ins、c_del、c_rep 都为 1 时，就是经典编辑距离（LeetCode 72）。
通过以上步骤，我们可以计算出任意自定义代价下的最短编辑距离。