最小插入次数构造回文串问题（相邻字符交换允许）

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

1. 插入一个字符，成本为 insertCost。
2. 交换相邻的两个字符，成本为 swapCost。

目标是通过这些操作将 s 变成回文串，并使得总成本最小。求最小总成本。
注意：交换操作允许任意次数，且每次交换只能发生在相邻字符之间。

解题思路
这是一个区间动态规划问题。我们定义 dp[i][j] 为将子串 s[i:j+1] 变成回文串的最小成本。我们需要考虑如何通过操作匹配两端的字符。

状态转移分析
对于区间 [i, j]，我们有以下几种情况：

1. 如果 s[i] == s[j]，两端字符已经匹配，直接处理内部子串 [i+1, j-1]，成本为 dp[i+1][j-1]。
2. 如果 s[i] != s[j]，我们需要通过操作使两端匹配，有三种策略：
   • 在左端插入一个字符匹配右端：在 i 的左边插入 s[j]，成本为 insertCost + dp[i][j-1]。
   • 在右端插入一个字符匹配左端：在 j 的右边插入 s[i]，成本为 insertCost + dp[i+1][j]。
   • 通过交换将右端字符移到左端：通过相邻交换将 s[j] 移动到 i 的位置，交换次数为 (j - i)，成本为 swapCost * (j - i) + dp[i+1][j-1]（注意移动后原 s[j] 被移除，区间变为 [i+1, j-1]）。

状态转移方程：

if s[i] == s[j]:
    dp[i][j] = dp[i+1][j-1]
else:
    dp[i][j] = min(
        insertCost + dp[i][j-1],    # 左插右字符
        insertCost + dp[i+1][j],    # 右插左字符
        swapCost * (j - i) + dp[i+1][j-1]  # 交换右字符到左端
    )

边界条件

• 当 i == j，子串长度为 1，已经是回文，成本为 0。
• 当 i > j，空子串，成本为 0。

详细步骤

1. 初始化一个二维数组 dp，大小为 n x n（n 为字符串长度），初始值设为无穷大。
2. 处理长度为 1 的子串：对所有 i，dp[i][i] = 0。
3. 按子串长度 L 从 2 到 n 遍历：
   • 遍历起始下标 i，计算结束下标 j = i + L - 1。
   • 根据状态转移方程计算 dp[i][j]。
4. 最终结果存储在 dp[0][n-1] 中。

示例
设 s = "ab"，insertCost = 1，swapCost = 2。

• 区间 [0,1]：s[0]='a'，s[1]='b'，不匹配。
  • 左插 'b'：成本 = 1 + dp[0][0] = 1 + 0 = 1。
  • 右插 'a'：成本 = 1 + dp[1][1] = 1 + 0 = 1。
  • 交换：成本 = 2 × (1-0) + dp[1][0]（无效区间，成本0） = 2。
  • 最小成本 = min(1, 1, 2) = 1。

复杂度分析

• 时间复杂度：O(n²)，需要填充 O(n²) 状态的 DP 表。
• 空间复杂度：O(n²)，用于存储 DP 表。