区间动态规划例题：合并相邻字符的最小成本问题（字符替换与删除的进阶版）

题目描述

给定一个字符串s，以及两个操作：

1. 删除任意位置的字符，每次删除操作的成本为deleteCost
2. 替换任意位置的字符为另一个字符，每次替换操作的成本为replaceCost

现在要求通过一系列操作将字符串s变成回文串，求最小的总操作成本。

解题思路

这个问题可以用区间动态规划来解决。我们定义dp[i][j]表示将子串s[i..j]变成回文串所需的最小成本。

状态转移分析

对于任意区间[i, j]，我们考虑首尾字符s[i]和s[j]：

1. 如果s[i] == s[j]

   • 首尾字符已经相等，不需要额外操作
   • 成本等于将内部子串s[i+1..j-1]变成回文串的成本
   • dp[i][j] = dp[i+1][j-1]

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

   • 删除s[i]：成本 = deleteCost + dp[i+1][j]
   • 删除s[j]：成本 = deleteCost + dp[i][j-1]
   • 替换其中一个字符：让s[i] = s[j]或s[j] = s[i]
     • 成本 = replaceCost + dp[i+1][j-1]

   取这三种情况的最小值。

边界条件

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

详细解题步骤

让我们通过一个具体例子来理解：s = "abc", deleteCost = 1, replaceCost = 1

步骤1：初始化DP表

字符串长度 n = 3
dp[i][j] 表示将 s[i..j] 变成回文的最小成本

初始化对角线（单个字符）：
dp[0][0] = 0
dp[1][1] = 0  
dp[2][2] = 0

步骤2：计算长度为2的子串

• 子串"ab" (i=0, j=1)：

  • s[0]='a' ≠ s[1]='b'
  • 删除'a'：1 + dp[1][1] = 1 + 0 = 1
  • 删除'b'：1 + dp[0][0] = 1 + 0 = 1
  • 替换：1 + dp[1][0] = 1 + 0 = 1
  • dp[0][1] = min(1, 1, 1) = 1

• 子串"bc" (i=1, j=2)：

  • s[1]='b' ≠ s[2]='c'
  • 同理可得 dp[1][2] = 1

步骤3：计算长度为3的子串

子串"abc" (i=0, j=2)：

• s[0]='a' ≠ s[2]='c'
• 删除'a'：1 + dp[1][2] = 1 + 1 = 2
• 删除'c'：1 + dp[0][1] = 1 + 1 = 2
• 替换：1 + dp[1][1] = 1 + 0 = 1
• dp[0][2] = min(2, 2, 1) = 1

最终结果：dp[0][2] = 1

算法实现

def min_cost_to_palindrome(s, deleteCost, replaceCost):
    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]:
                # 首尾字符相等
                if i + 1 <= j - 1:
                    dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = 0  # 长度为2且首尾相等
            else:
                # 首尾字符不等
                cost1 = deleteCost + dp[i+1][j]  # 删除s[i]
                cost2 = deleteCost + dp[i][j-1]  # 删除s[j]
                cost3 = replaceCost + dp[i+1][j-1]  # 替换
                dp[i][j] = min(cost1, cost2, cost3)
    
    return dp[0][n-1]

复杂度分析

• 时间复杂度：O(n²)，需要填充n×(n+1)/2个状态
• 空间复杂度：O(n²)，DP表的大小

这个算法通过系统地处理所有可能的子区间，确保了找到将任意字符串转换为回文串的最小成本方案。