最长公共子序列的变种：带字符插入/删除/替换代价的最短编辑距离（进阶版：带位置相关的操作代价）

题目描述
给定两个字符串 word1 和 word2，以及三种操作的代价函数：

1. 插入操作：在第 i 个字符后插入一个字符，代价为 ins_cost(i, ch)。
2. 删除操作：删除 word1 的第 i 个字符，代价为 del_cost(i, ch)。
3. 替换操作：将 word1 的第 i 个字符替换为 word2 的第 j 个字符，代价为 rep_cost(i, j, ch1, ch2)。

注意：代价函数可能依赖于位置和字符本身。
目标：计算将 word1 转换为 word2 的最小总代价。

示例
假设：

• word1 = "abc", word2 = "adc"
• 插入代价：在任意位置插入任意字符，代价为 1
• 删除代价：删除任意位置字符，代价为 1
• 替换代价：若字符相同则为 0，否则为 2

则最小代价为 0（因为只需替换 'b' 为 'd'，但此处 'b' != 'd'，所以替换代价为 2，但也可以删除 'b' 再插入 'd'，总代价 1+1=2）。
最终结果为 2。

解题思路
这是编辑距离问题的泛化版本，核心仍然是动态规划。但代价函数与位置相关，因此状态设计需包含当前处理到的位置。

步骤 1：状态定义
设 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最小代价。
这里 i 从 0 到 len(word1)，j 从 0 到 len(word2)。
注意：word1 的前 i 个字符下标是 0 到 i-1。

步骤 2：初始状态

• dp[0][0] = 0：两个空字符串无需操作。
• dp[i][0]：将 word1 的前 i 个字符全部删除，代价为删除这些字符的代价之和。
  即：dp[i][0] = dp[i-1][0] + del_cost(i-1, word1[i-1])。
• dp[0][j]：从空串构造 word2 的前 j 个字符，全部插入，代价为插入这些字符的代价之和。
  即：dp[0][j] = dp[0][j-1] + ins_cost(j-1, word2[j-1])（注意：插入位置可能是前一个字符之后，此处假设 ins_cost(k, ch) 表示在已构建的长度为 k 的字符串后插入 ch 的代价，但题目中 ins_cost(i, ch) 的 i 是原 word1 的位置索引，这里需根据题意调整，常见简化为代价与位置无关，我们先按与位置相关但只依赖原串位置来推导）。

步骤 3：状态转移方程
考虑从 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] 转移到 dp[i][j]：

1. 替换或保持：
   将 word1[i-1] 替换为 word2[j-1]。
   若 word1[i-1] == word2[j-1]，则替换代价可能是 0 或由 rep_cost 决定。
   总代价 = dp[i-1][j-1] + rep_cost(i-1, j-1, word1[i-1], word2[j-1])。
2. 删除：
   删除 word1[i-1]，然后处理 word1 前 i-1 个字符到 word2 前 j 个字符。
   总代价 = dp[i-1][j] + del_cost(i-1, word1[i-1])。
3. 插入：
   在 word1 的前 i 个字符后（即当前已处理到 i 的位置）插入 word2[j-1]，然后处理 word1 前 i 个字符到 word2 前 j-1 个字符。
   总代价 = dp[i][j-1] + ins_cost(i-1, word2[j-1])（这里 ins_cost 的第一个参数表示在 word1 的第 i-1 个字符后插入，如果 i=0 则表示在开头插入，需根据题意定义）。

取三者最小值：
dp[i][j] = min( replace_cost, delete_cost, insert_cost )

步骤 4：边界与细节

• 如果 ins_cost、del_cost、rep_cost 是常数函数，则退化为标准编辑距离。
• 如果代价与位置相关，在递推时需传入当前下标。
• 注意索引：word1 的第 i 个字符下标是 i-1。
• 如果 ins_cost 的第一个参数表示“在原串的第 k 个字符后插入”，那么在 dp[i][j-1] 转移到 dp[i][j] 时，我们已经用掉了 word1 的前 i 个字符，下一个插入位置可以认为是第 i 个字符后（即下标 i-1 之后），所以用 ins_cost(i-1, word2[j-1]) 是合理的。
• 如果 i=0，表示在原串开头插入，此时 ins_cost 可能需要特殊定义（比如 ins_cost(-1, ch) 表示在开头插入）。在代码中可特殊处理。

步骤 5：举例演算
假设 word1 = "ab", word2 = "bc"，代价函数简化为常数：ins=1, del=1, rep=2。
dp 表大小 3×3。

初始化：

• dp[0][0] = 0
• dp[1][0] = dp[0][0] + del('a') = 0+1=1
• dp[2][0] = dp[1][0] + del('b') = 1+1=2
• dp[0][1] = dp[0][0] + ins('b') = 0+1=1
• dp[0][2] = dp[0][1] + ins('c') = 1+1=2

计算 dp[1][1]（"a"→"b"）：

• 替换：dp[0][0] + rep('a','b') = 0+2=2
• 删除：dp[0][1] + del('a') = 1+1=2
• 插入：dp[1][0] + ins('b') = 1+1=2
  dp[1][1] = 2

计算 dp[1][2]（"a"→"bc"）：

• 替换：dp[0][1] + rep('a','b') = 1+2=3
• 删除：dp[0][2] + del('a') = 2+1=3
• 插入：dp[1][1] + ins('c') = 2+1=3
  dp[1][2] = 3

计算 dp[2][1]（"ab"→"b"）：

• 替换：dp[1][0] + rep('b','b') = 1+0=1
• 删除：dp[1][1] + del('b') = 2+1=3
• 插入：dp[2][0] + ins('b') = 2+1=3
  dp[2][1] = 1

计算 dp[2][2]（"ab"→"bc"）：

• 替换：dp[1][1] + rep('b','c') = 2+2=4
• 删除：dp[1][2] + del('b') = 3+1=4
• 插入：dp[2][1] + ins('c') = 1+1=2
  dp[2][2] = 2

最小代价为 2。

步骤 6：算法复杂度
时间复杂度 O(mn)，空间复杂度 O(mn)（可优化到 O(min(m, n))）。

步骤 7：代码框架（Python）

def min_edit_distance_cost(word1, word2, ins_cost, del_cost, rep_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] = dp[i-1][0] + del_cost(i-1, word1[i-1])
    
    # 初始化插入所有字符的代价
    for j in range(1, n+1):
        # 在开头插入的特殊处理，假设 ins_cost(-1, ch) 表示在开头插入
        dp[0][j] = dp[0][j-1] + ins_cost(j-2 if j>1 else -1, word2[j-1])
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            replace = dp[i-1][j-1] + rep_cost(i-1, j-1, word1[i-1], word2[j-1])
            delete = dp[i-1][j] + del_cost(i-1, word1[i-1])
            # 插入 word2[j-1] 在 word1 的第 i-1 字符后
            insert = dp[i][j-1] + ins_cost(i-1, word2[j-1])
            dp[i][j] = min(replace, delete, insert)
    
    return dp[m][n]

总结
这个问题是编辑距离的泛化，关键在于代价函数与位置相关时，状态转移时需传入正确的索引。实际应用中，代价函数可能以查表形式给出，只需在计算时获取对应代价即可。