合并相邻同色方块的最小成本问题（字符替换与删除）

题目描述

给定一个由小写字母组成的字符串s，每次操作可以：

1. 删除一个字符，成本为deleteCost
2. 将一个字符替换为另一个字符，成本为replaceCost

目标是通过这些操作，使得最终字符串中所有相邻的字符都不相同，求最小总成本。

解题过程

1. 问题分析
这个问题要求我们通过删除和替换操作，消除字符串中所有相邻的相同字符。我们需要找到成本最低的操作序列。

2. 状态定义
定义dp[i][j]表示将子串s[i...j]处理成满足条件（相邻字符不同）的最小成本。

3. 状态转移方程

考虑子串s[i...j]：

• 如果i == j（单个字符），dp[i][j] = 0（已经满足条件）
• 如果i > j，dp[i][j] = 0（空串）

对于一般情况i < j：

• 情况1：删除字符s[i]，成本为deleteCost + dp[i+1][j]
• 情况2：保留字符s[i]，但需要考虑与后面字符的匹配

当保留s[i]时，我们需要找到第一个位置k（i < k ≤ j），使得s[i] ≠ s[k]，然后：

• 将s[i+1...k-1]的所有字符处理掉（删除或替换）
• 然后递归处理s[k...j]

具体来说：
dp[i][j] = min(
deleteCost + dp[i+1][j], // 删除s[i]
min_{k从i+1到j} {
dp[i+1][k-1] + replaceCost × (k-i-1) + dp[k][j]
（当s[i] ≠ s[k]时）
}
)

4. 边界条件

• 当i > j时，dp[i][j] = 0
• 当i == j时，dp[i][j] = 0

5. 计算顺序
由于dp[i][j]依赖于dp[i+1][k-1]和dp[k][j]，其中k > i，所以我们需要：

• 按子串长度从小到大计算
• 对于每个起始位置i，从右往左计算

6. 算法实现

def min_cost_to_remove_adjacent_duplicates(s, deleteCost, replaceCost):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 按子串长度从小到大计算
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # 情况1：删除第一个字符
            option1 = deleteCost + dp[i+1][j]
            
            # 情况2：保留第一个字符，找到第一个不同的字符位置
            option2 = float('inf')
            for k in range(i+1, j+1):
                if s[i] != s[k]:
                    # 将i+1到k-1的字符处理掉，然后处理k到j
                    cost_between = dp[i+1][k-1] + replaceCost * (k - i - 1)
                    option2 = min(option2, cost_between + dp[k][j])
            
            dp[i][j] = min(option1, option2)
    
    return dp[0][n-1]

7. 示例说明

考虑字符串s = "aab"，deleteCost = 1，replaceCost = 2：

• 子串"aa"：

  • 删除第一个'a'：成本1 + dp[1][1] = 1 + 0 = 1
  • 保留第一个'a'：找到位置1，s[0]='a'≠s[1]='a'？不满足条件
  • 所以最小成本是1

• 完整字符串"aab"：

  • 删除第一个'a'：成本1 + dp[1]2 = 1 + 0 = 1
  • 保留第一个'a'：找到位置2，s[0]='a'≠s[2]='b'
    • 处理"a"（位置1）：成本dp[1][1] + 2×1 = 0 + 2 = 2
    • 加上dp[2][2] = 0，总成本2
  • 最小成本min(1, 2) = 1

8. 时间复杂度优化
基础实现的时间复杂度是O(n³)，可以通过预处理来优化到O(n²)。

这个算法通过动态规划系统地考虑了所有可能的操作序列，确保找到成本最低的解决方案。