合并字符串形成目标串的最小插入成本问题

字数 2331 2025-11-29 19:18:23

合并字符串形成目标串的最小插入成本问题

题目描述
给定两个字符串 s 和 t，以及一个插入操作的成本函数。每次操作可以在字符串 s 的任意位置插入一个字符，插入字符 c 的成本为 cost[c]。你的目标是通过若干次插入操作，将字符串 s 变成字符串 t，并使得总插入成本最小。求最小的总成本。

解题思路
这个问题可以通过区间动态规划来解决。我们定义 dp[i][j] 表示将 s 的子串 s[i:j]（左闭右开区间）通过插入操作匹配到 t 的某个子串所需的最小成本。但更常见的定义是：dp[i][j] 表示将 s 的前 i 个字符通过插入操作匹配到 t 的前 j 个字符所需的最小成本。

步骤详解

状态定义
设 dp[i][j] 表示将 s 的前 i 个字符转换成 t 的前 j 个字符所需的最小插入成本。
初始状态
- 当 i = 0 且 j = 0 时，两个空字符串匹配，成本为 0：dp[0][0] = 0
- 当 i = 0 时，s 为空，需要插入 t 的前 j 个字符，成本为这些字符的插入成本之和：dp[0][j] = dp[0][j-1] + cost[t[j-1]]
- 当 j = 0 时，t 为空，但 s 非空，无法通过插入操作（只能插入不能删除）使 s 变成空串，因此这种情况不可能，设为无穷大：dp[i][0] = inf（i > 0）
状态转移方程
考虑如何从 dp[i][j] 的前驱状态转移过来：
- 如果 s[i-1] == t[j-1]，当前字符匹配，不需要插入操作，直接继承前一个状态：dp[i][j] = dp[i-1][j-1]
- 如果 s[i-1] != t[j-1]，我们有两种选择：
  - 在 s 中插入字符 t[j-1]，成本为 cost[t[j-1]]，然后匹配 s 的前 i 个字符和 t 的前 j-1 个字符：dp[i][j-1] + cost[t[j-1]]
  - 忽略 s 的当前字符（但题目不允许删除，所以这种选择不适用）
    实际上，由于只能插入，当字符不匹配时，我们只能插入 t[j-1]，因此：dp[i][j] = dp[i][j-1] + cost[t[j-1]]
但注意：如果 s[i-1] 不能直接匹配 t[j-1]，我们可能需要在 s 的当前位置之前插入 t[j-1]，使得后续的 s[i-1] 可能匹配 t 中更后面的字符。因此，更通用的转移方程是：
- dp[i][j] = min( dp[i][j-1] + cost[t[j-1]], dp[i-1][j] )? 不对，因为不能删除 s 的字符。
  正确的思考：我们总是尝试匹配 s 和 t 的当前字符，如果匹配就消掉，否则插入 t 的当前字符。所以：
```
如果 s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1]
否则:
    dp[i][j] = dp[i][j-1] + cost[t[j-1]]
```
但这样会漏掉一种情况：如果 s[i-1] 出现在 t 的更早位置，我们可能需要在 s 中插入多个字符才能让 s[i-1] 匹配到 t 的对应字符。所以我们需要考虑 s 的字符可以匹配 t 中任意位置的相同字符（只要顺序一致）。这实际上是一个最长公共子序列（LCS）的变种，其中插入成本代替了编辑距离中的操作权重。

更精确的解法是：我们寻找 s 和 t 的一个最长公共子序列（LCS），然后对于 t 中不在 LCS 的字符，我们需要插入。因此，最小成本 = t 中所有字符的插入成本之和减去 LCS 中字符的插入成本（因为这些字符不需要插入）。但 LCS 可能有多个，我们要找使“LCS中字符的插入成本之和”最大的那个 LCS。

因此，问题转化为：求 s 和 t 的带权最长公共子序列（WLCS），其中每个字符的权重是它的插入成本。那么最小插入成本 = t 的总插入成本 - WLCS 的权重和。
动态规划求 WLCS
定义 wlcs[i][j] 为 s 前 i 个字符和 t 前 j 个字符的带权最长公共子序列的权重和。
- 初始：wlcs[0][j] = 0, wlcs[i][0] = 0
- 转移：
  - 如果 s[i-1] == t[j-1]：wlcs[i][j] = wlcs[i-1][j-1] + cost[t[j-1]]
  - 否则：wlcs[i][j] = max(wlcs[i-1][j], wlcs[i][j-1])
那么最小插入成本 = sum(cost[t[k]] for k in range(len(t))) - wlcs[len(s)][len(t)]
最终结果
计算 t 的总成本，然后减去 wlcs[len(s)][len(t)] 即为答案。

示例
设 s = "abc", t = "adbec", cost = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5}

t 总成本 = 1+4+2+5+3 = 15
LCS 为 "abc"，权重和 = 1+2+3 = 6
最小插入成本 = 15 - 6 = 9（需要插入 d 和 e，成本 4+5=9）

复杂度分析

时间复杂度：O(mn)，其中 m 和 n 分别是 s 和 t 的长度。
空间复杂度：O(mn)，可优化到 O(min(m, n))。

通过这个思路，我们可以将插入成本最小化问题转化为寻找带权最长公共子序列的问题，从而利用区间动态规划高效求解。

合并字符串形成目标串的最小插入成本问题题目描述给定两个字符串 s 和 t ，以及一个插入操作的成本函数。每次操作可以在字符串 s 的任意位置插入一个字符，插入字符 c 的成本为 cost[c] 。你的目标是通过若干次插入操作，将字符串 s 变成字符串 t ，并使得总插入成本最小。求最小的总成本。解题思路这个问题可以通过区间动态规划来解决。我们定义 dp[i][j] 表示将 s 的子串 s[i:j] （左闭右开区间）通过插入操作匹配到 t 的某个子串所需的最小成本。但更常见的定义是： dp[i][j] 表示将 s 的前 i 个字符通过插入操作匹配到 t 的前 j 个字符所需的最小成本。步骤详解状态定义设 dp[i][j] 表示将 s 的前 i 个字符转换成 t 的前 j 个字符所需的最小插入成本。初始状态当 i = 0 且 j = 0 时，两个空字符串匹配，成本为 0： dp[0][0] = 0 当 i = 0 时， s 为空，需要插入 t 的前 j 个字符，成本为这些字符的插入成本之和： dp[0][j] = dp[0][j-1] + cost[t[j-1]] 当 j = 0 时， t 为空，但 s 非空，无法通过插入操作（只能插入不能删除）使 s 变成空串，因此这种情况不可能，设为无穷大： dp[i][0] = inf （ i > 0 ）状态转移方程考虑如何从 dp[i][j] 的前驱状态转移过来：如果 s[i-1] == t[j-1] ，当前字符匹配，不需要插入操作，直接继承前一个状态： dp[i][j] = dp[i-1][j-1] 如果 s[i-1] != t[j-1] ，我们有两种选择：在 s 中插入字符 t[j-1] ，成本为 cost[t[j-1]] ，然后匹配 s 的前 i 个字符和 t 的前 j-1 个字符： dp[i][j-1] + cost[t[j-1]] 忽略 s 的当前字符（但题目不允许删除，所以这种选择不适用）实际上，由于只能插入，当字符不匹配时，我们只能插入 t[j-1] ，因此： dp[i][j] = dp[i][j-1] + cost[t[j-1]] 但注意：如果 s[i-1] 不能直接匹配 t[j-1] ，我们可能需要在 s 的当前位置之前插入 t[j-1] ，使得后续的 s[i-1] 可能匹配 t 中更后面的字符。因此，更通用的转移方程是： dp[i][j] = min( dp[i][j-1] + cost[t[j-1]], dp[i-1][j] ) ? 不对，因为不能删除 s 的字符。正确的思考：我们总是尝试匹配 s 和 t 的当前字符，如果匹配就消掉，否则插入 t 的当前字符。所以：但这样会漏掉一种情况：如果 s[i-1] 出现在 t 的更早位置，我们可能需要在 s 中插入多个字符才能让 s[i-1] 匹配到 t 的对应字符。所以我们需要考虑 s 的字符可以匹配 t 中任意位置的相同字符（只要顺序一致）。这实际上是一个最长公共子序列（LCS）的变种，其中插入成本代替了编辑距离中的操作权重。更精确的解法是：我们寻找 s 和 t 的一个最长公共子序列（LCS），然后对于 t 中不在 LCS 的字符，我们需要插入。因此，最小成本 = t 中所有字符的插入成本之和减去 LCS 中字符的插入成本（因为这些字符不需要插入）。但 LCS 可能有多个，我们要找使“LCS中字符的插入成本之和”最大的那个 LCS。因此，问题转化为：求 s 和 t 的带权最长公共子序列（WLCS），其中每个字符的权重是它的插入成本。那么最小插入成本 = t 的总插入成本 - WLCS 的权重和。动态规划求 WLCS 定义 wlcs[i][j] 为 s 前 i 个字符和 t 前 j 个字符的带权最长公共子序列的权重和。初始： wlcs[0][j] = 0 , wlcs[i][0] = 0 转移：如果 s[i-1] == t[j-1] ： wlcs[i][j] = wlcs[i-1][j-1] + cost[t[j-1]] 否则： wlcs[i][j] = max(wlcs[i-1][j], wlcs[i][j-1]) 那么最小插入成本 = sum(cost[t[k]] for k in range(len(t))) - wlcs[len(s)][len(t)] 最终结果计算 t 的总成本，然后减去 wlcs[len(s)][len(t)] 即为答案。示例设 s = "abc" , t = "adbec" , cost = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5} t 总成本 = 1+4+2+5+3 = 15 LCS 为 "abc" ，权重和 = 1+2+3 = 6 最小插入成本 = 15 - 6 = 9（需要插入 d 和 e ，成本 4+5=9）复杂度分析时间复杂度：O(mn)，其中 m 和 n 分别是 s 和 t 的长度。空间复杂度：O(mn)，可优化到 O(min(m, n))。通过这个思路，我们可以将插入成本最小化问题转化为寻找带权最长公共子序列的问题，从而利用区间动态规划高效求解。