合并字符串形成回文串的最小插入成本问题
字数 2714 2025-12-23 09:13:59

合并字符串形成回文串的最小插入成本问题

题目描述

给你一个字符串 s，你可以执行以下操作任意次：

  • 在字符串的任意位置插入一个小写英文字母，每次插入的成本是固定的，但不同字符的插入成本可能不同（题目会给出每个字符的插入成本表）。

问：最少需要多少总插入成本，才能将原字符串 s 变成回文串？

示例
假设字符串 s = "abca"，字母插入成本为：a:1, b:2, c:3。
一种方法：在开头插入 'a'，得到 "aabca"，总成本 = 1（插入 'a' 的成本）。
另一种方法：在末尾插入 'c'，得到 "abcac"，总成本 = 3。
最优解：在末尾插入 'a'，得到 "abcba"（需先处理对称性），实际需要插入 2 个字符？我们下面会分析。

实际上，我们可以通过动态规划计算最小成本，而不是直观猜测。

为什么这是区间 DP 问题

要将整个字符串变成回文，我们可以从两边向中间考虑：

  • 如果 s[i] == s[j]，那么这两个字符已经配对，不需要在它们之间插入新字符来匹配它们，只需考虑内部子串 (i+1, j-1) 变成回文的最小成本。
  • 如果 s[i] != s[j]，有两种方式让它们匹配：
    1. 在 j 的右边插入一个字符等于 s[i]，成本是 cost[s[i]]，然后问题变成子串 (i+1, j) 变成回文。
    2. 在 i 的左边插入一个字符等于 s[j]，但注意在 DP 中，我们可视为“在子串 (i, j-1) 的右边插入 s[j]”，成本是 cost[s[j]]，然后问题变成子串 (i, j-1) 变成回文。

这样，状态就只依赖于更小的区间，符合区间 DP 的特征。

动态规划定义

定义 dp[i][j] 为将子串 s[i..j] 变成回文串的最小插入成本。

  • 当 i > j 时，子串为空，已经是回文，成本 0。
  • 当 i == j 时，单个字符，已经是回文，成本 0。

转移方程：

  1. 如果 s[i] == s[j]：
    • 如果 j == i+1，即两个相同字符相邻，已经是回文，成本 0。
    • 否则，dp[i][j] = dp[i+1][j-1]（因为这两个字符已经匹配，只需处理中间部分）。
  2. 如果 s[i] != s[j]：
    • 选择 1：在 j 右边插入 s[i]，成本 = cost[s[i]] + dp[i+1][j]。
    • 选择 2：在 i 左边插入 s[j]，成本 = cost[s[j]] + dp[i][j-1]。
    • 取两者最小值。

即：

\[dp[i][j] = \begin{cases} dp[i+1][j-1] & \text{if } s[i] = s[j] \\ \min(cost[s[i]] + dp[i+1][j],\ cost[s[j]] + dp[i][j-1]) & \text{if } s[i] \neq s[j] \end{cases} \]

最终答案：dp[0][n-1]，其中 n 是字符串长度。

逐步示例计算

设 s = "abca"，cost[a]=1, cost[b]=2, cost[c]=3。
n = 4，下标 0~3。

初始化：dp[i][i] = 0 对所有 i。

按区间长度 len 从 2 到 4 计算：

len=2:

  • [0,1]: s[0]=a, s[1]=b 不同
    dp[0][1] = min(cost[a]+dp[1][1], cost[b]+dp[0][0])
    = min(1+0, 2+0) = 1（在 b 右边插入 a 成本更低）

  • [1,2]: s[1]=b, s[2]=c 不同
    = min(cost[b]+dp[2][2], cost[c]+dp[1][1])
    = min(2+0, 3+0) = 2

  • [2,3]: s[2]=c, s[3]=a 不同
    = min(3+0, 1+0) = 1

len=3:

  • [0,2]: s[0]=a, s[2]=c 不同
    = min(cost[a]+dp[1][2], cost[c]+dp[0][1])
    = min(1+2, 3+1) = min(3,4) = 3

  • [1,3]: s[1]=b, s[3]=a 不同
    = min(cost[b]+dp[2][3], cost[a]+dp[1][2])
    = min(2+1, 1+2) = min(3,3) = 3

len=4:

  • [0,3]: s[0]=a, s[3]=a 相同
    dp[0][3] = dp[1][2] = 2

最终结果：dp[0][3] = 2。

验证：原串 "abca" 如何以成本 2 变回文？

  • 在末尾插入 'b'（成本 2），得到 "abcab"，是回文吗？不是。
    我们仔细看 dp 过程：实际上最优是：
    看 [0,3] 相同，用 [1,2] 的结果 2，表示里面 "bc" 变回文成本 2。
    "bc" 变回文：在 c 右边插入 b（成本 2），得到 "bcb"，所以整体是 "a"+"bcb"+"a" = "abcba"，成本=2。
    对，这就是最优解。

复杂度与实现细节

  • 时间复杂度：O(n²)，状态数 n²，转移 O(1)。
  • 空间复杂度：O(n²)，可优化到 O(n) 用滚动数组，但通常直接二维数组即可。

实现要点：

  1. 外层循环枚举区间长度 len 从 2 到 n。
  2. 内层循环枚举起点 i，计算 j = i+len-1。
  3. 注意当 s[i]==s[j] 时，如果 j=i+1，则 dp[i][j]=0，这被包含在 dp[i+1][j-1] 中，因为 dp[i+1][j-1] 中 i+1>j-1 时返回 0，但代码中通常直接处理：
    • 若 j==i+1 且相同，dp[i][j]=0。
    • 否则 dp[i][j]=dp[i+1][j-1]。

核心思想总结

这个区间 DP 问题本质是“通过插入字符使字符串回文”，与经典的“最小插入次数”问题相似，但每次插入成本不同。

  • 当两端字符相等时，直接由内层子问题得到。
  • 当两端不等时，选择成本更小的字符插入来匹配另一端，然后转化为长度减 1 的子问题。

这样，我们就能在多项式时间内求出最小成本，而不需要枚举所有可能的插入位置与字符。

合并字符串形成回文串的最小插入成本问题 题目描述 给你一个字符串 s ，你可以执行以下操作任意次： 在字符串的任意位置插入一个小写英文字母，每次插入的成本是固定的，但不同字符的插入成本可能不同（题目会给出每个字符的插入成本表）。 问：最少需要多少总插入成本，才能将原字符串 s 变成回文串？ 示例 假设字符串 s = "abca" ，字母插入成本为： a:1 , b:2 , c:3 。 一种方法：在开头插入 'a' ，得到 "aabca" ，总成本 = 1（插入 'a' 的成本）。 另一种方法：在末尾插入 'c' ，得到 "abcac" ，总成本 = 3。 最优解：在末尾插入 'a' ，得到 "abcba" （需先处理对称性），实际需要插入 2 个字符？我们下面会分析。 实际上，我们可以通过动态规划计算最小成本，而不是直观猜测。 为什么这是区间 DP 问题 要将整个字符串变成回文，我们可以从两边向中间考虑： 如果 s[i] == s[j] ，那么这两个字符已经配对，不需要在它们之间插入新字符来匹配它们，只需考虑内部子串 (i+1, j-1) 变成回文的最小成本。 如果 s[i] != s[j] ，有两种方式让它们匹配： 在 j 的右边插入一个字符等于 s[i] ，成本是 cost[s[i]] ，然后问题变成子串 (i+1, j) 变成回文。 在 i 的左边插入一个字符等于 s[j] ，但注意在 DP 中，我们可视为“在子串 (i, j-1) 的右边插入 s[j] ”，成本是 cost[s[j]] ，然后问题变成子串 (i, j-1) 变成回文。 这样，状态就只依赖于更小的区间，符合区间 DP 的特征。 动态规划定义 定义 dp[i][j] 为将子串 s[i..j] 变成回文串的最小插入成本。 当 i > j 时，子串为空，已经是回文，成本 0。 当 i == j 时，单个字符，已经是回文，成本 0。 转移方程 ： 如果 s[i] == s[j] ： 如果 j == i+1 ，即两个相同字符相邻，已经是回文，成本 0。 否则， dp[i][j] = dp[i+1][j-1] （因为这两个字符已经匹配，只需处理中间部分）。 如果 s[i] != s[j] ： 选择 1：在 j 右边插入 s[i] ，成本 = cost[s[i]] + dp[i+1][j] 。 选择 2：在 i 左边插入 s[j] ，成本 = cost[s[j]] + dp[i][j-1] 。 取两者最小值。 即： \[ dp[ i][ j ] = \begin{cases} dp[ i+1][ j-1] & \text{if } s[ i] = s[ j ] \\ \min(cost[ s[ i]] + dp[ i+1][ j],\ cost[ s[ j]] + dp[ i][ j-1]) & \text{if } s[ i] \neq s[ j ] \end{cases} \] 最终答案 ： dp[0][n-1] ，其中 n 是字符串长度。 逐步示例计算 设 s = "abca" ， cost[a]=1, cost[b]=2, cost[c]=3 。 n = 4，下标 0~3。 初始化： dp[i][i] = 0 对所有 i。 按区间长度 len 从 2 到 4 计算 ： len=2: [ 0,1]: s[ 0]=a, s[ 1 ]=b 不同 dp[0][1] = min(cost[a]+dp[1][1], cost[b]+dp[0][0]) = min(1+0, 2+0) = 1（在 b 右边插入 a 成本更低） [ 1,2]: s[ 1]=b, s[ 2 ]=c 不同 = min(cost[ b]+dp[ 2][ 2], cost[ c]+dp[ 1][ 1 ]) = min(2+0, 3+0) = 2 [ 2,3]: s[ 2]=c, s[ 3 ]=a 不同 = min(3+0, 1+0) = 1 len=3: [ 0,2]: s[ 0]=a, s[ 2 ]=c 不同 = min(cost[ a]+dp[ 1][ 2], cost[ c]+dp[ 0][ 1 ]) = min(1+2, 3+1) = min(3,4) = 3 [ 1,3]: s[ 1]=b, s[ 3 ]=a 不同 = min(cost[ b]+dp[ 2][ 3], cost[ a]+dp[ 1][ 2 ]) = min(2+1, 1+2) = min(3,3) = 3 len=4: [ 0,3]: s[ 0]=a, s[ 3 ]=a 相同 dp[0][3] = dp[1][2] = 2 最终结果 ： dp[0][3] = 2 。 验证：原串 "abca" 如何以成本 2 变回文？ 在末尾插入 'b'（成本 2），得到 "abcab"，是回文吗？不是。 我们仔细看 dp 过程：实际上最优是： 看 [ 0,3] 相同，用 [ 1,2 ] 的结果 2，表示里面 "bc" 变回文成本 2。 "bc" 变回文：在 c 右边插入 b（成本 2），得到 "bcb"，所以整体是 "a"+"bcb"+"a" = "abcba"，成本=2。 对，这就是最优解。 复杂度与实现细节 时间复杂度：O(n²)，状态数 n²，转移 O(1)。 空间复杂度：O(n²)，可优化到 O(n) 用滚动数组，但通常直接二维数组即可。 实现要点 ： 外层循环枚举区间长度 len 从 2 到 n。 内层循环枚举起点 i，计算 j = i+len-1。 注意当 s[ i]==s[ j] 时，如果 j=i+1，则 dp[ i][ j]=0，这被包含在 dp[ i+1][ j-1] 中，因为 dp[ i+1][ j-1 ] 中 i+1>j-1 时返回 0，但代码中通常直接处理： 若 j==i+1 且相同，dp[ i][ j ]=0。 否则 dp[ i][ j]=dp[ i+1][ j-1 ]。 核心思想总结 这个区间 DP 问题本质是“通过插入字符使字符串回文”，与经典的“最小插入次数”问题相似，但每次插入成本不同。 当两端字符相等时，直接由内层子问题得到。 当两端不等时，选择成本更小的字符插入来匹配另一端，然后转化为长度减 1 的子问题。 这样，我们就能在多项式时间内求出最小成本，而不需要枚举所有可能的插入位置与字符。