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

题目描述

给定一个字符串s和一个二维数组cost，其中cost[i][j]表示将字符i替换为字符j的代价（i和j是字符的ASCII码值）。另外，删除任意字符的代价是固定的，设为deleteCost。

你可以执行以下两种操作任意次数：

1. 删除字符串中的一个字符，代价为deleteCost
2. 将字符串中的一个字符替换为另一个字符，代价由cost数组给出

求将整个字符串变成空字符串的最小总代价。

解题思路

这个问题可以用区间动态规划来解决。我们定义dp[i][j]表示将子串s[i...j]变成空字符串的最小代价。

状态转移分析

对于任意区间[i, j]，我们考虑以下几种情况：

1. 直接删除所有字符：代价为 (j-i+1) * deleteCost

2. 先处理部分区间，再处理剩余部分：
   对于任意k (i ≤ k < j)，将区间分成[i, k]和[k+1, j]两部分分别处理：
   dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

3. 当s[i] == s[j]时的特殊情况：
   如果首尾字符相同，我们可以考虑一种更优的策略：将中间的部分变成空字符串后，首尾字符可以一起删除（因为相同字符的删除可能有特殊处理）

详细解题步骤

1. 初始化：

   • 创建二维数组dp，大小为n×n，其中n是字符串长度
   • 初始化所有单个字符的删除代价

2. 状态转移方程：

   # 情况1：直接删除所有字符
   dp[i][j] = (j-i+1) * deleteCost
   
   # 情况2：分割区间
   for k in range(i, j):
       dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
   
   # 情况3：首尾字符相同时的特殊处理
   if s[i] == s[j]:
       # 可以选择将中间部分清空后，一起处理首尾字符
       dp[i][j] = min(dp[i][j], dp[i+1][j-1] + min(deleteCost * 2, cost[s[i]][s[i]]))
   

3. 遍历顺序：

   • 按区间长度从小到大遍历
   • 对于每个区间长度，遍历所有可能的起始位置

完整代码示例

def min_cost_to_empty_string(s, cost, deleteCost):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 初始化单个字符的情况
    for i in range(n):
        dp[i][i] = deleteCost  # 直接删除单个字符
    
    # 按区间长度从小到大遍历
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # 情况1：直接删除所有字符
            dp[i][j] = length * deleteCost
            
            # 情况2：分割区间
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
            
            # 情况3：首尾字符相同
            if s[i] == s[j]:
                if length == 2:
                    # 只有两个相同字符，可以选择一起删除或分别删除
                    dp[i][j] = min(dp[i][j], min(deleteCost * 2, cost[ord(s[i])][ord(s[i])]))
                else:
                    # 多个字符，先处理中间部分
                    dp[i][j] = min(dp[i][j], dp[i+1][j-1] + min(deleteCost * 2, cost[ord(s[i])][ord(s[i])]))
    
    return dp[0][n-1]

复杂度分析

• 时间复杂度：O(n³)，需要三重循环
• 空间复杂度：O(n²)，用于存储dp数组

举例说明

假设字符串s = "abacaba"，deleteCost = 2，cost矩阵中相同字符替换代价为0，不同字符替换代价为很大的数。

处理过程：

1. 单个字符：直接删除，代价2
2. 两个字符"ab"：分别删除代价4，或替换再删除，选择较小代价
3. 逐步扩展到整个字符串，利用子问题的解来构建更大区间的解

这个算法通过动态规划有效地找到了将字符串变成空字符串的最小代价。