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

题目描述：
给定一个字符串s，你可以重复执行以下操作：

1. 删除一个字符，成本为deleteCost
2. 替换一个字符为另一个字符，成本为replaceCost
3. 合并两个相邻的相同字符为一个字符，成本为0

目标是通过这些操作，最终将字符串合并为一个字符，求最小总成本。

解题过程：

步骤1：理解问题

• 我们有三种操作：删除、替换、合并
• 合并操作只对相邻的相同字符有效，且成本为0
• 最终目标是将整个字符串合并成一个字符
• 我们需要找到成本最小的操作序列

步骤2：定义状态
设dp[i][j]表示将子串s[i...j]合并为一个字符所需的最小成本。

步骤3：状态转移分析
对于区间[i,j]，我们考虑以下几种情况：

情况1：直接处理
如果区间长度为1，即i == j，那么dp[i][j] = 0，因为不需要任何操作。

情况2：字符相同可以合并
如果s[i] == s[k]（i < k ≤ j），我们可以考虑将区间分成两部分处理：

• 先处理[i,k-1]得到字符s[i]
• 再处理[k,j]得到字符s[k]（即s[i]）
• 由于两个字符相同，可以免费合并
  dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k][j])

情况3：字符不同需要替换或删除
如果首尾字符不同，我们需要通过替换或删除操作：

• 替换：dp[i][j] = min(dp[i][j], dp[i+1][j] + replaceCost)
• 删除：dp[i][j] = min(dp[i][j], dp[i+1][j] + deleteCost)

步骤4：完整的状态转移方程
dp[i][j] = min(
// 情况1：删除第一个字符
dp[i+1][j] + deleteCost,

// 情况2：替换第一个字符
dp[i+1][j] + replaceCost,

// 情况3：寻找相同字符进行合并
min_{i<k≤j, s[i]==s[k]} (dp[i][k-1] + dp[k][j])

)

步骤5：边界条件

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

步骤6：计算顺序
我们需要按照区间长度从小到大计算：

1. 长度为1的区间
2. 长度为2的区间
3. ......
4. 长度为n的区间

步骤7：示例演示
考虑字符串s = "aba"，deleteCost = 2，replaceCost = 1

初始化：
dp[0][0] = 0, dp[1][1] = 0, dp[2][2] = 0

长度为2的区间：

• = min(dp[1][1] + deleteCost, dp[1][1] + replaceCost) = min(0+2, 0+1) = 1
• = min(dp[2][2] + deleteCost, dp[2][2] + replaceCost) = min(0+2, 0+1) = 1

长度为3的区间[0,2]: "aba"
情况1：删除'a' + 处理"ba" = 2 + 1 = 3
情况2：替换'a' + 处理"ba" = 1 + 1 = 2
情况3：找到相同字符

• k=2时，s[0]=s[2]='a'
  dp[0][1] + dp[2][2] = 1 + 0 = 1
  最小值为1

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

步骤8：算法复杂度

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

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