合并字符串形成目标串的最小插入成本问题（带位置权重） 题目描述 给定两个字符串 s 和 t ，以及一个二维数组 cost[i][j] ，表示在字符串 s 的第 i 个字符（下标从1开始）之后 插入 一个字符（这个字符是 t 的第 j 个字符）所需的花费。目标是通过在 s 中插入若干个字符（包括在开头、结尾和任意位置插入），使得 s 最终变成 t 。每次插入可以选择 t 中的任意字符，但需要支付对应的位置权重成本。求完成转换的最小总插入成本。 注意 ： 原始字符串 s 中的字符 不能删除或修改 ，只能通过在任意位置插入新字符来形成目标串 t 。 插入操作有“位置权重”：在 s 的第 i 个字符之后插入（ i=0 表示在开头前插入），且插入的字符是 t 的第 j 个字符时，成本为 cost[i][j] 。 题目保证 s 是 t 的一个 子序列 （即 s 可以通过删除 t 中的某些字符得到），因此一定有解。 长度： s 长度为 n ， t 长度为 m ， 1 ≤ n, m ≤ 200 ， cost 数组大小为 (n+1) × m ，每个值为非负整数。 解题思路 这个问题本质上是“在保持 s 原有字符顺序不变的前提下，通过插入补齐缺失的字符，使得最终序列等于 t ”。由于插入操作有位置权重，不能简单地贪心匹配。我们可以用区间DP来规划在 s 的某个区间与 t 的某个子串的匹配过程中，如何以最小成本插入字符。 定义状态 定义 dp[i][j] 表示：已经考虑将 s 的前 i 个字符（下标1到i）转换为 t 的前 j 个字符（下标1到j）所需的最小插入成本。 i 范围是 0 到 n （ i=0 表示 s 中还没有字符被考虑）。 j 范围是 0 到 m （ j=0 表示 t 为空）。 目标：求 dp[n][m] 。 状态转移 我们考虑当前状态 dp[i][j] ，即已经匹配了 s[1..i] 和 t[1..j] ，现在要决定下一步： 如果 s[i] == t[j] ： 那么当前字符可以直接匹配，不需要插入，所以： dp[i][j] = dp[i-1][j-1] （即两个字符自然对齐，无成本）。 如果 s[i] != t[j] ： 由于不能删除或修改 s 的字符，我们必须通过 在 s 的前 i 个字符之后插入字符 来匹配 t[j] 。 但插入字符有一个关键：插入的字符必须是 t 中的某个字符，并且有位置权重。我们可以考虑“在 s 的第 k 个字符之后插入 t[j] ”，其中 k 是插入位置（ 0 ≤ k ≤ i ）。 但这样直接枚举插入位置会使状态转移复杂。 更巧妙的方式是： 我们换个角度， dp[i][j] 表示在已经匹配了 s[1..i] 和 t[1..j] 时，最后一个操作可能是： 匹配了 s[i] 和 t[j] （当它们相等时，成本为0）。 或者，我们在某个位置插入了 t[j] 这个字符，然后让 s[1..i] 去匹配 t[1..j-1] 。 但这样又有一个问题：插入 t[j] 的位置权重取决于“在 s 的哪个字符之后插入”，而那个位置在之前的状态中可能已经改变了。 为了处理位置权重，我们需要在状态中记录“当前在 s 中最后一个被使用的字符的位置”，因为插入成本与这个位置有关。 因此，我们 扩展状态 ： 定义 dp[i][j][k] 表示：将 s 的前 i 个字符匹配到 t 的前 j 个字符，并且 最后一次插入操作是在 s 的第 k 个字符之后执行的 （ k=0 表示在开头之前）的最小成本。 但这样状态是 O(n*m*n) ，在 n,m ≤ 200 时可能过大（800万状态，每个状态转移需 O(n) 可能超时）。 我们可以优化：注意到插入位置只与 s 的字符索引有关，我们可以将“插入位置”作为状态的一个维度，但我们可以用另一种等价方式： 考虑用区间DP，定义 dp[l][r][p] 表示：将 s 的子串 s[l..r] 转换为 t 的子串 t[p..q] 的最小成本，但这样还需要记录 q ，状态太多。 回到线性DP的改进版本： 定义 dp[i][j] 为：将 s[1..i] 转换为 t[1..j] 的最小成本，且 我们只记录成本，插入位置信息通过比较 i 和匹配的字符来隐式处理 。 正确的状态转移： 对于 dp[i][j] ： 如果 s[i] == t[j] ：我们可以直接匹配， dp[i][j] = dp[i-1][j-1] 。 无论如何，我们也可以选择在 s 的第 i 个字符之后插入 t[j] （这是允许的，因为插入可以在任何位置）。插入成本是 cost[i][j] 。插入后， t[j] 被匹配，而 s 的前 i 个字符仍然需要匹配 t 的前 j-1 个字符，所以： dp[i][j] = min(dp[i][j], dp[i][j-1] + cost[i][j]) 。 此外，我们还可以在更早的位置（比如在第 i-1 个字符之后）插入 t[j] ，但这种情况已经被 dp[i][j-1] 覆盖了吗？不一定，因为 dp[i][j-1] 表示 s[1..i] 匹配 t[1..j-1] ，它的最后一次插入位置可能是 i 或更小。如果我们在位置 k 插入 t[j] ，那相当于从 dp[i][j-1] 的状态再插入一个字符，但插入位置权重是 cost[k][j] ，而这个 k 是之前的状态决定的，我们不知道。 所以我们需要在状态中记录“最后一个字符在原串 s 中的匹配位置”，才能确定下一次插入的位置权重。 重新设计状态： 定义 dp[i][j][k] 表示：将 s[1..i] 转换为 t[1..j] ，并且 在 s 中最后一个被匹配的字符是 s[ k] （即下一个插入位置将在 s[ k ] 之后）的最小成本。 i 和 j 含义同上。 k 范围 0 到 i，表示最后一个匹配的 s 的字符索引（k=0 表示还没匹配任何 s 的字符，即全在开头之前插入）。 初始状态： dp[0][0][0] = 0 ，其他为无穷大。 转移： 如果 s[i] == t[j] 且 i>0, j>0： 我们可以让 s[i] 匹配 t[j] ，那么最后一个匹配的 s 字符变为 i，所以： dp[i][j][i] = min(dp[i][j][i], dp[i-1][j-1][k]) 对所有 k。 我们可以在位置 k（0 ≤ k ≤ i）之后插入字符 t[j] ，那么状态会从 dp[i][j-1][k] 转移来，因为插入前匹配到 t 的前 j-1 个字符，且最后一个匹配的 s 字符是 k，在 k 后插入 t[ j] 的成本是 cost[k][j] ，插入后最后一个匹配的 s 字符 不变 （因为插入的不是 s 的字符），所以： dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][k] + cost[k][j]) 。 注意：插入操作不改变 i，因为 s 的长度没变（插入的字符是额外的，不算在 s 的原始字符里）。 这个状态是 O(n*m*n) ，在 n=m=200 时是 800 万，每个状态转移是 O(1)，可以接受。 最终答案： min(dp[n][m][k]) 对所有 k。 逐步演算（小例子） 设 s = "ab" , t = "acb" , n=2, m=3。 cost 表（简化，假设 cost 都=1 除非特殊）： cost[ 0][ 1]=1, cost[ 0][ 2]=1, cost[ 0][ 3 ]=1 cost[ 1][ 1]=1, cost[ 1][ 2]=1, cost[ 1][ 3 ]=1 cost[ 2][ 1]=1, cost[ 2][ 2]=1, cost[ 2][ 3 ]=1 初始化：dp[ 0][ 0][ 0 ]=0。 从 dp[ 0][ 0][ 0]，考虑插入 t[ 1 ]='a' 在位置 0 后： dp[ 0][ 1][ 0] = dp[ 0][ 0][ 0] + cost[ 0][ 1 ] = 1。 从 dp[ 0][ 1][ 0]，插入 t[ 2 ]='c' 在位置 0 后： dp[ 0][ 2][ 0] = 1 + cost[ 0][ 2 ] = 2。 从 dp[ 0][ 2][ 0]，插入 t[ 3 ]='b' 在位置 0 后： dp[ 0][ 3][ 0] = 2 + cost[ 0][ 3 ] = 3。 现在考虑 s[ 1]='a' 匹配 t[ 1 ]='a'： 从 dp[ 0][ 0][ 0] 转移：dp[ 1][ 1][ 1 ] = 0。 从 dp[ 1][ 1][ 1]，插入 t[ 2 ]='c' 在位置 1 后： dp[ 1][ 2][ 1] = 0 + cost[ 1][ 2 ] = 1。 从 dp[ 1][ 2][ 1]，插入 t[ 3 ]='b' 在位置 1 后： dp[ 1][ 3][ 1] = 1 + cost[ 1][ 3 ] = 2。 但 s[ 2]='b' 匹配 t[ 3 ]='b'： 可以从 dp[ 1][ 2][ 1] 转移：dp[ 2][ 3][ 2 ] = 1。 比较：最终 dp[ 2][ 3][ 2 ]=1 更小，所以最小成本=1。 算法步骤 初始化三维数组 dp[ n+1][ m+1][ n+1]，值设为无穷大，dp[ 0][ 0][ 0 ]=0。 循环 i 从 0 到 n： 循环 j 从 0 到 m： 循环 k 从 0 到 i： 如果 dp[ i][ j][ k ] 无穷大，跳过。 如果 i < n 且 j < m 且 s[ i+1]==t[ j+1 ]： dp[ i+1][ j+1][ i+1] = min(dp[ i+1][ j+1][ i+1], dp[ i][ j][ k ])。 如果 j < m： dp[ i][ j+1][ k] = min(dp[ i][ j+1][ k], dp[ i][ j][ k] + cost[ k][ j+1 ])。 最终答案 = min(dp[ n][ m][ k ]) 对所有 k。 时间复杂度 O(n²* m)，空间可优化为滚动数组 O(n²)。