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

题目描述
给定两个字符串 s1 和 s2，以及三个操作（插入、删除、替换）的代价。每次操作可以将一个字符插入 s1、从 s1 删除一个字符，或将 s1 的一个字符替换为另一个字符。目标是通过一系列操作将 s1 转换为 s2，并使得总操作代价最小。要求设计动态规划算法求解最小总代价。

解题过程

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

   • i 的取值范围：0 ≤ i ≤ len(s1)
   • j 的取值范围：0 ≤ j ≤ len(s2)

2. 初始化边界情况

   • 当 i = 0 时，s1 为空，只能通过插入 j 个字符得到 s2 的前 j 个字符：
     dp[0][j] = j * cost_insert（cost_insert 为插入一个字符的代价）
   • 当 j = 0 时，s2 为空，只能通过删除 i 个字符将 s1 变为空字符串：
     dp[i][0] = i * cost_delete（cost_delete 为删除一个字符的代价）

3. 状态转移方程
   对于一般情况 i > 0 且 j > 0，考虑对 s1 的第 i 个字符（即 s1[i-1]）的三种操作：

   • 删除：删除 s1[i-1]，问题转化为将 s1 的前 i-1 个字符转换为 s2 的前 j 个字符，代价为：
     dp[i-1][j] + cost_delete
   • 插入：在 s1 的第 i 个位置后插入 s2[j-1]，问题转化为将 s1 的前 i 个字符转换为 s2 的前 j-1 个字符，代价为：
     dp[i][j-1] + cost_insert
   • 替换：
     • 若 s1[i-1] == s2[j-1]，无需替换，直接继承子问题代价：dp[i-1][j-1]
     • 否则，将 s1[i-1] 替换为 s2[j-1]，代价为：dp[i-1][j-1] + cost_replace（cost_replace 为替换代价）

   综合上述情况，状态转移方程为：

   dp[i][j] = min(
        dp[i-1][j] + cost_delete,                    # 删除
        dp[i][j-1] + cost_insert,                    # 插入
        dp[i-1][j-1] + (0 if s1[i-1] == s2[j-1] else cost_replace)  # 替换或匹配
   )
   

4. 计算顺序与最终答案

   • 按 i 从 0 到 len(s1)，j 从 0 到 len(s2) 的顺序填充 dp 表。
   • 最终答案为 dp[len(s1)][len(s2)]，即整个字符串转换的最小代价。

示例
设 s1 = "horse", s2 = "ros"，操作代价均为 1（标准编辑距离）：

• 计算 dp 表后得到最小代价为 3（删除 h、替换 r 为 o、删除 e）。
  若替换代价为 2，则最小代价为 4（通过删除和插入操作避免高代价替换）。

关键点

• 通过自定义代价，可灵活处理不同场景（如替换代价较高时倾向于插入/删除）。
• 时间复杂度 O(mn)，空间复杂度可通过滚动数组优化至 O(min(m, n))。