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

问题描述

给你一个字符串 s，你可以进行以下两种操作任意多次：

1. 删除操作：删除字符串中任意一个字符，代价为 deleteCost。
2. 合并操作：选择两个相邻且相同的字符，将它们合并成一个字符（合并后的字符与原字符相同），代价为 mergeCost。

你的目标是通过一系列操作，最终将字符串 s 变成一个空字符串。求达成目标的最小总成本。

示例

s = "aabb"
deleteCost = 1
mergeCost = 2

• 方案一：逐个删除所有字符，成本 = 4 × 1 = 4。
• 方案二：先合并相邻的 a（位置0和1），合并后字符串变为 "abb"，成本为 2；再合并相邻的 b（位置1和2），成本 2，字符串变为 "ab"；最后删除 "a" 和 "b"，成本各 1，总成本 = 2 + 2 + 1 + 1 = 6。
• 方案三：先删除一个 a（成本1），剩下 "abb"；然后合并两个 b（成本2），得到 "ab"；再删除 "a" 和 "b"（成本各1），总成本 = 1 + 2 + 1 + 1 = 5。

需要找到全局最小成本。

解题思路

这是一个典型的区间动态规划问题，因为合并操作只能作用于相邻且相同的字符，而删除操作可以针对任意字符。我们可以定义子问题为处理字符串的某个子区间 [i, j] 的最小成本。

1. 定义状态

设 dp[i][j] 表示将子串 s[i:j]（包含 i，不包含 j，即区间长度为 j-i）变成空字符串的最小成本。
我们最终要求的是 dp[0][n]，其中 n 是字符串长度。

2. 状态转移方程

对于区间 [i, j)，我们有两种基本选择：

1. 删除字符 s[i]：先删除 s[i]（代价 deleteCost），再处理剩余区间 [i+1, j)。
   因此：
   cost1 = deleteCost + dp[i+1][j]。

2. 合并操作：如果 s[i] 可以与后面某个相同字符合并，那么我们可以考虑将 s[i] 与某个 s[k]（i < k < j 且 s[i] == s[k]）进行合并。
   注意合并操作要求相邻且相同，但这里 s[i] 和 s[k] 中间可能有其他字符。如何实现合并呢？
   关键思路是：为了合并 s[i] 和 s[k]，我们需要先让它们相邻。这意味着我们要先处理掉中间的子串 [i+1, k)，使其变为空，这样 s[i] 和 s[k] 就相邻了。
   之后，合并这两个相同字符（代价 mergeCost），得到一个字符 s[i]（或 s[k]）留在原位置 i（合并后位置 i 处的字符仍是原来的字符）。
   然后我们继续处理从 i 到 j 的子串，但此时 s[k] 已经被合并消失，所以剩余区间是 [i, j) 去掉 s[k]，即 [i+1, k) 已为空，s[i] 和 s[k+1: j) 相邻。
   为了简化，我们可以将合并后的 s[i] 看作一个整体，然后继续处理 [i+1, j)（因为 s[k] 已经消失，相当于区间从 i+1 开始）。
   所以转移为：

   cost2 = dp[i+1][k] + mergeCost + dp[k][j]   // 注意这里 dp[k][j] 处理的是 s[k] 之后的区间
   

   更准确的解释：

   • 第一步：清空 [i+1, k) 使 s[i] 与 s[k] 相邻，代价 dp[i+1][k]。
   • 第二步：合并 s[i] 和 s[k]，代价 mergeCost，此时 s[i] 仍在，s[k] 消失。
   • 第三步：处理合并后的字符串，即从 i 开始（因为 s[i] 还在）到 j 结束，但 s[k] 已消失，所以实际上是处理 s[i] 和 s[k+1: j) 组成的子串。
     这个子串可以看作 s[i] 与原区间 [k+1, j) 的结合。但注意，合并后 s[i] 与 s[k+1] 相邻，所以区间变成了 [i, k)（这部分是空的除了开头的 s[i]）和 [k+1, j)。
     为了统一，我们可以重新定义状态：合并后，我们继续处理区间 [i, j)，但因为 s[k] 消失，相当于区间长度减少 1，s[i] 仍然在位置 i。
     但这样不便于直接递归。更好的方式是将合并后的字符看作仍然在位置 i，然后继续处理区间 [i+1, j)。
     为什么是 i+1？因为合并操作相当于我们去掉了 s[k]，但 s[i] 仍然保留，现在 s[i] 和原来的 s[k+1] 相邻，所以新的区间是 [i+1, j)（注意原来的 s[i+1] 到 s[k-1] 已经被清空）。
     所以总的转移方程是：

     dp[i][j] = min(
         deleteCost + dp[i+1][j],
         min_{k: i<k<j, s[i]==s[k]} (dp[i+1][k] + mergeCost + dp[k+1][j])
     )
     

     解释：
     • dp[i+1][k]：清空 s[i+1:k)，使 s[i] 和 s[k] 相邻。
     • mergeCost：合并 s[i] 和 s[k]，合并后 s[i] 保留，s[k] 消失。
     • dp[k+1][j]：处理 s[k+1: j) 这部分（因为 s[k] 已消失，所以直接从 k+1 开始）。
     • 注意合并后 s[i] 仍然在，但它已经与后面的字符相邻，所以我们在后续的递归中会处理它（可能在后面的步骤中被删除或与其他相同字符合并）。

3. 特殊情况：如果区间长度为 1（即 j == i+1），只能删除，所以 dp[i][i+1] = deleteCost。

3. 动态规划实现顺序

区间 DP 通常按区间长度从小到大计算。

• 初始化：dp[i][i] = 0（空区间成本为 0）。
• 对长度 len 从 1 到 n：
  • 对起点 i 从 0 到 n-len：
    计算 dp[i][i+len] 使用上述方程。

示例详解

以 s = "aabb", deleteCost = 1, mergeCost = 2 为例，n=4。

1. 初始化：

   dp[i][i] = 0 for i=0..4
   dp[i][i+1] = 1  (单个字符只能删除)
   

2. 长度 2 区间：

   • [0,2)="aa"：
     删除 a0：1 + dp[1][2]=1 → 2
     合并 a0 与 a1（k=1）：dp[1][1]=0 + 2 + dp[2][2]=0 → 2
     取 min(2,2)=2。
   • [1,3)="ab"：
     只能删除：删除 a→1 + dp[2][3]=1 → 2
     没有相同字符可合并。
   • [2,4)="bb"：类似 "aa"，dp=2。

3. 长度 3 区间：

   • [0,3)="aab"：
     删除 a0：1 + dp[1][3]（"ab"成本=2）→ 3
     合并 a0 与 a1（k=1）：dp[1][1]=0 + 2 + dp[2][3]=1 → 3
     合并 a0 与 ? 没有其他 a，所以取 3。
   • [1,4)="abb"：
     删除 a1：1 + dp[2][4]=2 → 3
     合并 a1 与 ? 没有其他 a，所以 3。
     合并 b2 与 b3（对于 i=2，但 i=1 是 a，不能合并 b）。
     注意这里我们是以 i=1 为起点，所以只能合并 s[1]='a'，没有相同字符，所以只有删除选项。

   这里我们发现需要更仔细：对于区间 [i,j)，我们只考虑以 s[i] 为左端点进行合并。合并必须针对 s[i] 和后面某个相同字符。

4. 长度 4 区间 [0,4)="aabb"：

   • 删除 a0：1 + dp[1][4]=3 → 4
   • 合并 a0 与 a1（k=1）：dp[1][1]=0 + 2 + dp[2][4]=2 → 4
   • 合并 a0 与 ? 没有其他 a。
     所以 dp[0][4] = 4？
     但我们示例中手工找到最小是 4（全部删除），与方案一吻合。

   等等，示例方案三成本 5 怎么来的？
   方案三：先删除 a0（成本1）→ "abb"，然后合并 b2 与 b3（成本2）→ "ab"，再删除 a 和 b（各1）总成本 5。
   这个操作序列在我们的状态转移中如何体现？
   在 "aabb" 中，我们可以在处理 "abb" 时合并两个 b（区间 [2,4) 内合并 b2 与 b3），但注意合并两个 b 时，b2 是区间的第一个字符，所以我们的状态转移允许在任何区间内进行合并，只要该区间的第一个字符与后面某个字符相同。
   所以方案三对应的 dp 路径是：

   • 删除 a0：1 + dp[1][4]
     而 dp[1][4]（"abb"）的计算中，可以选择合并 b2 与 b3（k=3）：
     dp[2][3]（"b"？不对，区间 [2,3)="b"，[3,4)="b"）
     实际上，对于区间 [1,4)="abb"：
     如果先删除 a1（成本1），剩下 "bb"，然后合并两个 b（成本2），再删除（成本1）总成本 4，所以 dp[1][4] 最小是 4？
     不对，我们算一下：
     区间 [1,4)="abb"：
     选项1：删除 a1 → 1 + dp[2][4]（"bb"成本=2）= 3
     选项2：合并 a1 与 ? 没有相同字符。
     所以 dp[1][4] = 3。
     那么 dp[0][4] = 1 + 3 = 4，还是 4。
     所以最小确实是 4（全部删除），不是 5。原来示例中我算错了，方案三总成本是 1+2+1+1=5，但 dp 得到更优解 4（直接删除所有）。
     验证：删除 a,a,b,b 各成本1，总4。
     所以动态规划给出了正确的最小成本。

算法总结

1. 定义 dp[i][j]：将子串 s[i:j] 清空的最小成本。
2. 转移方程：

   dp[i][j] = min(
       deleteCost + dp[i+1][j],
       min_{k: i<k<j, s[i]==s[k]} (dp[i+1][k] + mergeCost + dp[k+1][j])
   )
   

3. 初始化：
   • dp[i][i] = 0。
   • 对长度为 1 的区间，dp[i][i+1] = deleteCost。
4. 按区间长度从小到大计算，最终返回 dp[0][n]。

复杂度分析

• 时间复杂度：O(n³)，因为对每个区间 [i,j)，需要枚举中间位置 k（最坏 O(n)）。
• 空间复杂度：O(n²)，用于存储 dp 表。

这个问题的核心是合并操作要求相邻相同字符，因此需要通过清空中间子串使两个相同字符相邻，这正是区间 DP 能自然处理的结构。通过比较删除成本与合并成本，我们可以找到最优策略。