合并相邻字符的最小成本问题（字符替换与删除的进阶版）

题目描述：
给定一个字符串s和一个成本数组cost，其中cost[i]表示删除或替换字符s[i]的成本。你可以执行两种操作：

1. 删除任意位置的字符，成本为cost[i]
2. 替换任意位置的字符为另一个字符，成本为cost[i]

目标是通过一系列操作使得字符串变成回文串，并且总成本最小。

解题过程：

1. 问题分析：

• 我们需要将字符串转换为回文串，这意味着对于任意位置i，s[i]应该等于s[n-1-i]（其中n是字符串长度）
• 对于不匹配的字符对，我们有三种选择：
  a. 删除左边的字符
  b. 删除右边的字符
  c. 替换其中一个字符使它们相等
• 这是一个典型的区间动态规划问题，因为我们需要考虑字符串的各个子区间

2. 状态定义：
   定义dp[i][j]表示将子串s[i...j]转换为回文串的最小成本

3. 状态转移方程：
   对于区间[i, j]，考虑首尾字符s[i]和s[j]：

情况1：如果s[i] == s[j]

• 不需要额外操作，直接考虑内部子串：dp[i][j] = dp[i+1][j-1]

情况2：如果s[i] != s[j]
我们有三种选择：

• 删除s[i]：dp[i][j] = cost[i] + dp[i+1][j]
• 删除s[j]：dp[i][j] = cost[j] + dp[i][j-1]
• 替换操作（两种选择）：
  • 将s[i]替换为s[j]：dp[i][j] = cost[i] + dp[i+1][j-1]
  • 将s[j]替换为s[i]：dp[i][j] = cost[j] + dp[i+1][j-1]

因此：dp[i][j] = min(cost[i] + dp[i+1][j], cost[j] + dp[i][j-1],
cost[i] + dp[i+1][j-1], cost[j] + dp[i+1][j-1])

4. 边界条件：

• 当i > j时，空字符串已经是回文串，dp[i][j] = 0
• 当i == j时，单个字符本身就是回文串，dp[i][j] = 0

5. 计算顺序：
   由于dp[i][j]依赖于dp[i+1][j], dp[i][j-1], dp[i+1][j-1]，我们需要按区间长度从小到大计算

6. 算法实现：

def min_cost_to_palindrome(s, cost):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 按区间长度从小到大计算
    for length in range(2, n + 1):  # 长度从2到n
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] if i+1 <= j-1 else 0
            else:
                option1 = cost[i] + dp[i+1][j]      # 删除s[i]
                option2 = cost[j] + dp[i][j-1]      # 删除s[j]
                option3 = cost[i] + (dp[i+1][j-1] if i+1 <= j-1 else 0)  # 替换s[i]
                option4 = cost[j] + (dp[i+1][j-1] if i+1 <= j-1 else 0)  # 替换s[j]
                dp[i][j] = min(option1, option2, option3, option4)
    
    return dp[0][n-1]

7. 示例验证：
   假设s = "abc", cost = [1, 2, 1]

• 区间[0,2]：s[0]='a' ≠ s[2]='c'
• 比较四种选择：
  • 删除'a'：1 + dp[1,2] = 1 + min(删除'b'或'c'或替换) = 1 + min(2,1,2,1) = 1 + 1 = 2
  • 删除'c'：1 + dp[0,1] = 1 + min(删除'a'或'b'或替换) = 1 + min(1,2,1,2) = 1 + 1 = 2
  • 替换'a'为'c'：1 + dp[1,1] = 1 + 0 = 1
  • 替换'c'为'a'：1 + dp[1,1] = 1 + 0 = 1
• 最小成本为1

8. 复杂度分析：

• 时间复杂度：O(n²)，需要填充n×(n+1)/2个状态
• 空间复杂度：O(n²)，用于存储dp表

这个算法通过系统地考虑所有可能的操作组合，确保了找到将字符串转换为回文串的最小成本方案。