合并字符串的最小成本问题（带权值版本，允许插入、删除、替换，且操作有不同成本）
题目描述
给你两个字符串 s 和 t，以及三种操作的成本：
- 插入一个字符，成本为
ins_cost。 - 删除一个字符，成本为
del_cost。 - 将一个字符替换成另一个字符，成本为
rep_cost（如果字符相同，则替换成本为 0）。
你需要将字符串 s 转换成字符串 t，求最小总成本。
注意：这里的“替换”操作允许将字符 s[i] 改成任意字符（包括与原来相同），但只有字符相同时成本为 0，否则为 rep_cost。
例如：
s = "abc", t = "adc", ins_cost = 1, del_cost = 1, rep_cost = 1。
最小成本是 1（将 'b' 替换为 'd'）。
解题思路
这是一道经典的编辑距离问题的变种，但这里我们明确用区间动态规划的思路来推导，以加深对区间DP的理解。
我们可以定义子问题为：将 s 的某个前缀转换成 t 的某个前缀的最小成本。但为了更贴合“区间”的概念，我们考虑从两个字符串的任意子串角度出发。
然而，更常见的解法是二维DP，但我们可以把它看作是一种“双区间”DP：
- 定义
dp[i][j]为将s的前i个字符转换成t的前j个字符的最小成本。 - 这里“区间”指的是
s[0..i-1]和t[0..j-1]这两个区间。
但为了更符合“区间DP”的框架，我们可以想象为同时对两个序列的区间进行操作，不过这类问题更常见的名称是“序列对齐”，而不是狭义的“单序列区间划分”。不过我们可以把它理解为在两个序列上的区间DP（即区间长度变化）。
详细步骤
1. 定义状态
设 dp[i][j] 表示将 s 的前 i 个字符（即 s[0..i-1]）转换成 t 的前 j 个字符（即 t[0..j-1]）的最小成本。
这里 i 和 j 分别表示两个字符串的前缀长度，取值范围：
i从 0 到m（m是s的长度）j从 0 到n（n是t的长度）
初始条件：
dp[0][0] = 0（两个空串转换成本为0）dp[i][0] = i * del_cost（删除s的前i个字符）dp[0][j] = j * ins_cost（插入t的前j个字符到空串）
2. 状态转移方程
对于 dp[i][j]，我们考虑最后一步操作：
-
删除
s的第i个字符（即s[i-1]）：
此时我们已经将s[0..i-2]转换成了t[0..j-1]，然后删除s[i-1]。
成本 =dp[i-1][j] + del_cost -
插入
t的第j个字符（即t[j-1]）：
此时我们已经将s[0..i-1]转换成了t[0..j-2]，然后插入t[j-1]。
成本 =dp[i][j-1] + ins_cost -
替换（或保留）
s[i-1]为t[j-1]：
我们先让s[0..i-2]转换成t[0..j-2]，然后看s[i-1]和t[j-1]是否相同。- 如果相同，则不需要替换，成本 =
dp[i-1][j-1] - 如果不同，则替换，成本 =
dp[i-1][j-1] + rep_cost
- 如果相同，则不需要替换，成本 =
取三者最小值：
\[dp[i][j] = \min\begin{cases} dp[i-1][j] + del\_cost \\ dp[i][j-1] + ins\_cost \\ dp[i-1][j-1] + (s[i-1] == t[j-1] \;?\; 0 : rep\_cost) \end{cases} \]
3. 递推顺序
因为 dp[i][j] 依赖 i-1, j、i, j-1、i-1, j-1，所以可以按 i 从 0 到 m，j 从 0 到 n 的顺序计算。
4. 示例演算
以 s = "abc", t = "adc", ins_cost = 1, del_cost = 1, rep_cost = 1 为例。
初始化：
dp[0][0] = 0
dp[1][0] = 1 (删除a)
dp[2][0] = 2 (删除a,b)
dp[3][0] = 3
dp[0][1] = 1 (插入a)
dp[0][2] = 2
dp[0][3] = 3
计算 dp[1][1]：
- 删除：
dp[0][1] + 1 = 1+1=2 - 插入：
dp[1][0] + 1 = 1+1=2 - 替换/保留：
s[0]=a,t[0]=a相同，所以dp[0][0] + 0 = 0
最小值 = 0
计算 dp[1][2]：
- 删除：
dp[0][2] + 1 = 2+1=3 - 插入：
dp[1][1] + 1 = 0+1=1 - 替换：
s[0]=a,t[1]=d不同，dp[0][1] + 1 = 1+1=2
最小值 = 1
继续计算完表格：
最终 dp[3][3] 计算：
- 删除：
dp[2][3] + 1 = 1+1=2 - 插入：
dp[3][2] + 1 = 2+1=3 - 替换：
s[2]=c,t[2]=c相同，dp[2][2] + 0 = 1+0=1
最小值 = 1
所以最小成本是 1。
5. 时间复杂度与空间复杂度
- 时间复杂度：O(m*n)
- 空间复杂度：可以优化到 O(min(m, n)) 的滚动数组，但为了清晰，用 O(m*n) 也可以。
总结
这道题虽然本质是编辑距离，但用区间DP的思想（两个序列的区间对齐）可以自然推导。
关键点：
- 定义状态为两个前缀的转换最小成本。
- 从最后一步操作（删除、插入、替换）推导转移方程。
- 注意相同字符时替换成本为0。
通过这个例子，你能够掌握如何处理两个序列之间的最小转换成本问题，并理解如何将操作成本融入状态转移中。