最小成本构造回文串问题（字符插入、删除、替换）

题目描述
给定一个字符串 s 和三个整数 insertCost、deleteCost、replaceCost，分别表示插入一个字符、删除一个字符、替换一个字符的成本。每次操作可以在字符串的任意位置进行。要求通过若干次操作将 s 变成回文串，并返回最小总成本。

示例
输入：s = "abcda", insertCost = 1, deleteCost = 2, replaceCost = 3
输出：4
解释：一种方案是删除 'b'（成本2）并删除 'c'（成本2），总成本4，得到回文串 "ada"。

解题过程

1. 问题分析
目标是将任意字符串转换为回文串，允许三种操作：

• 插入：在任意位置插入一个字符（成本 = insertCost）
• 删除：删除任意位置的字符（成本 = deleteCost）
• 替换：将任意字符替换为另一个字符（成本 = replaceCost）

关键点：

• 回文串要求 s[i] == s[j] 对所有对称位置成立。
• 操作可以灵活组合，例如删除不对称字符或替换为相同字符。

2. 定义状态
使用区间动态规划，定义 dp[i][j] 表示将子串 s[i:j]（左闭右闭区间）变成回文串的最小成本。

基础情况：

• 当 i == j：单字符本身是回文，成本为0。
• 当 i > j：空串是回文，成本为0。

3. 状态转移方程
考虑子串 s[i:j]，比较首尾字符 s[i] 和 s[j]：

情况1：s[i] == s[j]
首尾字符已相等，无需额外操作，直接处理内部子串：
dp[i][j] = dp[i+1][j-1]

情况2：s[i] != s[j]
需要操作使两端字符匹配，有三种策略：

1. 删除左端字符：删除 s[i]，成本为 deleteCost，然后处理 s[i+1:j]：
   cost1 = deleteCost + dp[i+1][j]

2. 删除右端字符：删除 s[j]，成本为 deleteCost，然后处理 s[i:j-1]：
   cost2 = deleteCost + dp[i][j-1]

3. 插入匹配字符（两种对称方式）：

   • 在左端插入 s[j]，使 s[i] 和新增字符匹配，成本为 insertCost，然后处理 s[i:j-1]（因为 s[j] 已匹配）：
     cost3 = insertCost + dp[i][j-1]
   • 在右端插入 s[i]，成本为 insertCost，然后处理 s[i+1:j]：
     cost4 = insertCost + dp[i+1][j]
   • 注意：插入操作两种方式成本相同，可合并为一种情况。

4. 替换字符：将 s[i] 替换为 s[j]（或反之），成本为 replaceCost，然后处理内部子串：
   cost5 = replaceCost + dp[i+1][j-1]

状态转移方程：
dp[i][j] = min(cost1, cost2, cost3, cost5)
即：

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

简化：删除左端和插入右端效果类似（但成本可能不同），需保留所有选项。

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

• 外层循环：长度 L 从 2 到 n（长度为1时成本为0）
• 内层循环：起始下标 i 从 0 到 n-L，计算 j = i + L - 1

5. 示例推导
以 s = "abcda", insertCost=1, deleteCost=2, replaceCost=3 为例：

初始化：所有单字符子串成本为0。

长度=2：

• "ab"：
  • 删除'a'：2 + dp["b"] = 2 + 0 = 2
  • 删除'b'：2 + dp["a"] = 2
  • 在右插'a'：1 + dp["a"] = 1
  • 在左插'b'：1 + dp["b"] = 1
  • 替换：3 + dp[""] = 3
  • min = 1
• 类似计算其他长度为2的子串。

最终计算 dp[0][4]（完整字符串）时，会组合各子问题的最优解，得到最小成本4。

6. 复杂度分析

• 时间复杂度：O(n²)，需要填充 n×(n) 的DP表。
• 空间复杂度：O(n²)，可优化至O(n)（仅存储两行）。

通过以上步骤，即可求出将任意字符串转化为回文串的最小操作成本。