合并相邻字符的最小成本问题（字符删除与合并）
题目描述：
给定一个字符串s和一个成本数组cost，其中cost[i]表示删除字符s[i]的成本。你可以执行以下两种操作：
- 删除任意字符s[i]，成本为cost[i]
- 合并两个相邻的相同字符，成本为0
目标是通过这些操作，使得最终字符串中所有相邻字符都不相同，求达成目标的最小总成本。
解题过程：
1. 问题分析
这个问题要求我们通过删除或合并操作，消除字符串中所有相邻的相同字符。合并操作成本为0，但只能合并相邻的相同字符；删除操作有成本，但可以删除任意字符。
2. 状态定义
定义dp[i][j]表示处理子串s[i...j]所需的最小成本，其中0 ≤ i ≤ j < n。
3. 状态转移方程
情况1：直接删除第一个字符
如果我们选择删除第一个字符s[i]，那么成本为cost[i]加上处理子串s[i+1...j]的成本：
dp[i][j] = cost[i] + dp[i+1][j]
情况2：保留第一个字符，寻找匹配
如果我们保留第一个字符s[i]，那么我们需要在子串s[i+1...j]中寻找一个与s[i]相同的字符s[k]，将s[i]与s[k]之间的所有字符删除或处理，让s[i]和s[k]相邻然后合并。
对于所有k满足i < k ≤ j且s[i] == s[k]：
- 删除s[i+1...k-1]中的所有字符，成本为sum(cost[i+1...k-1])
- 处理子串s[k+1...j]，成本为dp[k+1][j]
- 合并s[i]和s[k]（成本为0）
因此：
dp[i][j] = min(dp[i][j], sum(cost[i+1...k-1]) + dp[k+1][j])
4. 边界条件
- 当i > j时，dp[i][j] = 0（空子串）
- 当i = j时，dp[i][j] = 0（单个字符，不需要处理）
5. 计算顺序
由于dp[i][j]依赖于dp[i+1][j]和dp[k+1][j]（其中k > i），我们需要按照子串长度从小到大的顺序计算：
- 先计算长度为1的子串
- 然后计算长度为2的子串
- 依此类推，直到计算整个字符串
6. 算法实现
def minCostToMergeAdjacentChars(s, cost):
n = len(s)
dp = [[0] * n for _ in range(n)]
# 前缀和数组，用于快速计算区间和
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + cost[i]
# 按子串长度从小到大计算
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
# 情况1：删除第一个字符
dp[i][j] = cost[i] + dp[i + 1][j]
# 情况2：寻找与s[i]相同的字符进行合并
for k in range(i + 1, j + 1):
if s[i] == s[k]:
# 计算s[i+1...k-1]的删除成本
delete_cost = prefix_sum[k] - prefix_sum[i + 1]
# 处理剩余部分
remaining_cost = dp[k + 1][j] if k + 1 <= j else 0
dp[i][j] = min(dp[i][j], delete_cost + remaining_cost)
return dp[0][n - 1]
7. 示例说明
考虑字符串s = "aabaa"，cost = [1, 2, 3, 4, 5]
计算过程：
- 子串"aa"：可以删除第一个'a'(成本1)或合并两个'a'(成本0)
- 子串"aab"：有多种处理方式，选择成本最小的
- 最终找到最优解：删除中间的'b'，合并所有相邻的'a'
8. 时间复杂度优化
当前算法时间复杂度为O(n³)，可以通过预处理和优化搜索来提升效率，但对于大多数实际问题已经足够高效。
这个解法通过动态规划系统地考虑了所有可能的操作序列，确保找到最小成本的解决方案。