线性动态规划：编辑距离（Edit Distance）的变种——带权编辑距离 题目描述 给定两个字符串 word1 和 word2 ，以及三个操作：插入（insert）、删除（delete）和替换（replace）。每个操作对不同字符可能具有不同的代价（权重）。要求计算将 word1 转换成 word2 所需的最小总代价。例如： 输入： word1 = "abc" , word2 = "adc" 操作代价：插入代价为 2，删除代价为 3，替换代价根据字符对而定（如 b 替换为 d 代价为 1，相同字符替换代价为 0）。 输出：最小总代价（此例中为 1，仅需一次替换）。 解题过程 定义状态 设 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小代价。 i 的取值范围： 0 到 len(word1) j 的取值范围： 0 到 len(word2) 初始化边界情况 当 i = 0 时， word1 为空，只能通过插入 j 个字符得到 word2 的前 j 个字符： dp[0][j] = dp[0][j-1] + insert_cost(word2[j-1]) 当 j = 0 时， word2 为空，只能通过删除 i 个字符将 word1 变为空： dp[i][0] = dp[i-1][0] + delete_cost(word1[i-1]) dp[0][0] = 0 （两个空字符串无需操作）。 状态转移方程 对于一般情况 dp[i][j] ，考虑最后一步可能执行的操作： 插入 ：在 word1 的前 i 个字符后插入 word2[j-1] ，代价为 insert_cost(word2[j-1]) 。此时需保证插入前 word1[0:i] 已匹配 word2[0:j-1] ，故： cost_insert = dp[i][j-1] + insert_cost(word2[j-1]) 删除 ：删除 word1 的第 i 个字符，代价为 delete_cost(word1[i-1]) 。删除后需保证 word1[0:i-1] 匹配 word2[0:j] ： cost_delete = dp[i-1][j] + delete_cost(word1[i-1]) 替换 ：将 word1[i-1] 替换为 word2[j-1] ，代价为 replace_cost(word1[i-1], word2[j-1]) 。若两字符相同，代价为 0。替换后需保证 word1[0:i-1] 匹配 word2[0:j-1] ： cost_replace = dp[i-1][j-1] + replace_cost(word1[i-1], word2[j-1]) 最终转移方程： dp[i][j] = min(cost_insert, cost_delete, cost_replace) 遍历顺序与计算 按 i 从 0 到 m （ m = len(word1) ）， j 从 0 到 n （ n = len(word2) ）的双重循环计算 dp[i][j] 。 注意：当 i = 0 或 j = 0 时直接使用初始化值，避免越界。 结果提取 最终结果为 dp[m][n] ，即整个 word1 转换为 word2 的最小代价。 示例演示 以 word1 = "abc" , word2 = "adc" 为例，假设代价函数为： insert_cost(char) = 2 delete_cost(char) = 3 replace_cost(a, a) = 0 ， replace_cost(b, d) = 1 ，其他替换代价为 10。 计算 dp 表（见下表），最终 dp[3][3] = 1 ，对应方案：保留 a ，将 b 替换为 d （代价 1），保留 c 。 | | j=0 | j=1 (a) | j=2 (d) | j=3 (c) | |-------|-----|---------|---------|---------| | i=0 | 0 | 2 | 4 | 6 | | i=1 (a)| 3 | 0 | 2 | 4 | | i=2 (b)| 6 | 3 | 1 | 3 | | i=3 (c)| 9 | 6 | 4 | 1 | 关键点 代价函数需预先定义，可能因字符而异。 若替换相同字符时代价为 0，则算法自动选择保留字符，避免无谓操作。 时间复杂度 O(mn)，空间复杂度可优化至 O(min(m, n))。