区间动态规划例题：最小插入次数构造回文串问题（字符插入与删除）

题目描述
给定一个字符串 s，你可以进行两种操作：

1. 插入一个字符，成本为 insertCost。
2. 删除一个字符，成本为 deleteCost。

目标是通过若干次操作将 s 变成回文串，且总成本最小。求最小成本。

示例

• 输入：s = "abac", insertCost = 1, deleteCost = 1
• 输出：1（删除 'b' 或插入 'c' 均可）

解题思路

1. 问题分析

• 回文串的特点是 s[i] 必须与 s[j] 匹配（i 和 j 为对称位置）。
• 若 s[i] != s[j]，可通过两种操作使其匹配：
  • 删除 s[i]：成本为 deleteCost，问题转化为子问题 [i+1, j]。
  • 删除 s[j]：成本为 deleteCost，问题转化为子问题 [i, j-1]。
  • 在 j 后插入 s[i]：成本为 insertCost，问题转化为 [i+1, j]（因为插入的字符与 s[i] 匹配，相当于跳过 s[i]）。
  • 在 i 前插入 s[j]：成本为 insertCost，问题转化为 [i, j-1]。
• 注意：插入和删除本质对称。例如，在左端插入等价于删除右端字符（成本可能不同）。

2. 状态定义
设 dp[i][j] 表示将子串 s[i:j] 变成回文的最小成本（i 和 j 为闭区间）。

3. 状态转移方程

• 基本情况：
  • 如果 i > j，子串为空，成本为 0。
  • 如果 i == j，单个字符已是回文，成本为 0。
• 一般情况（i < j）：
  • 若 s[i] == s[j]：两端字符已匹配，直接处理内部子串：

    dp[i][j] = dp[i+1][j-1]  
    

  • 若 s[i] != s[j]：考虑四种操作（可简化为两种对称操作）：

    dp[i][j] = min(  
        deleteCost + dp[i+1][j],    // 删除 s[i]  
        deleteCost + dp[i][j-1],    // 删除 s[j]  
        insertCost + dp[i+1][j],   // 在 j 后插入 s[i]  
        insertCost + dp[i][j-1]     // 在 i 前插入 s[j]  
    )  
    

    但注意：
    • deleteCost + dp[i+1][j] 与 insertCost + dp[i+1][j] 效果相同（均使问题变为 [i+1, j]），只需取较小值：min(deleteCost, insertCost) + dp[i+1][j]。
    • 同理，对右端操作：min(deleteCost, insertCost) + dp[i][j-1]。
    • 因此简化为：

      dp[i][j] = min(  
          min(deleteCost, insertCost) + dp[i+1][j],  
          min(deleteCost, insertCost) + dp[i][j-1]  
      )  
      

4. 计算顺序
按区间长度从小到大计算：

• 外层循环：长度 len 从 2 到 n。
• 内层循环：起点 i 从 0 到 n-len，终点 j = i+len-1。

5. 最终答案
dp[0][n-1] 即为整个字符串的最小成本。

举例说明

以 s = "abac", insertCost = 1, deleteCost = 1 为例：

1. 初始化 dp 表（4x4），对角线为 0。
2. 长度 len=2：
   • [0,1]："ab"，'a' != 'b'，dp[0][1] = min(1+dp[1][1], 1+dp[0][0]) = min(1+0, 1+0) = 1。
   • [1,2]："ba"，同理成本为 1。
   • [2,3]："ac"，成本为 1。
3. 长度 len=3：
   • [0,2]："aba"，首尾相同，dp[0][2] = dp[1][1] = 0。
   • [1,3]："bac"，首尾不同：

     dp[1][3] = min(1+dp[2][3], 1+dp[1][2]) = min(1+1, 1+1) = 2  
     

4. 长度 len=4：[0,3]："abac"，首尾相同（'a'），dp[0][3] = dp[1][2] = 1。
5. 最终结果：dp[0][3] = 1。

总结
本题通过区间 DP 将问题分解为子串的回文化成本，利用插入和删除操作的对称性简化状态转移。关键点是理解操作的可互换性，从而合并成本项。