区间动态规划例题：合并相邻同色方块的最小成本问题（相邻染色限制版本，进阶）

题目描述

假设有一个由字符组成的序列 s，长度为 n。每个字符可以看作一个方块，并有一个初始颜色。你的目标是通过一系列操作，将所有方块合并成同一个颜色。每次操作，你可以选择相邻的两个或多个同色方块，并将它们合并成一个方块，其颜色与原来的颜色相同。合并的成本为被合并的方块数量（即块数）的平方。例如，合并两个同色方块的成本是 2² = 4，合并三个同色方块的成本是 3² = 9。你可以在任意时刻，对任意一段连续的、颜色相同的方块进行合并。问：将所有方块合并成一个方块的最小总成本是多少？

示例：
输入：s = "aaabbbaa"
解释：初始序列可以看作 ['a','a','a','b','b','b','a','a']。一种可能的最优合并策略如下：

1. 合并前三个 'a'，成本 = 3² = 9，序列变为 ['AAA', 'b','b','b','a','a']，这里用 'AAA' 表示一个合并后的块。
2. 合并后两个 'a'，成本 = 2² = 4，序列变为 ['AAA', 'b','b','b','AA']。
3. 合并中间的三个 'b'，成本 = 3² = 9，序列变为 ['AAA', 'BBB', 'AA']。
4. 此时序列有三个不同颜色的块，需要继续合并。注意，合并只能合并相邻同色块，而 'AAA' 和 'AA' 虽然同色但不相邻，中间隔了 'BBB'。因此，需要先将某个块的颜色改变吗？不，题目不允许改变颜色，但可以通过合并相邻块来消除间隔。我们需要一种策略，在最终合并成一个块之前，可能需要先合并某些块，使得同色块相邻。
   实际上，对于这个例子，最优策略可能不同。让我们更严谨地描述问题。

重新澄清问题（更准确）：
实际上，这道题是“移除盒子”（Remove Boxes）问题的一种简化或变体，但更接近“合并相邻同色方块的最小成本”。这里我们给出标准的、常见的区间DP版本描述：

给定一个颜色序列 boxes（长度为 n），每个位置有一个颜色值（例如整数 1~k）。每次操作，你可以移除（或合并）一组连续的、颜色相同的方块。移除的成本是：移除的方块数量的平方。移除后，剩下的方块会并拢（即相邻）。你需要通过一系列这样的操作，移除所有方块。问：最小的总移除成本（或最大的总得分，如果是得分最大化问题，则成本对应负得分）？

但在本题中，我们关注最小成本版本。即，目标是找到一种移除顺序，使得移除所有方块的总成本（每次移除的方块数量的平方和）最小。

这比经典的“移除盒子”问题（求最大得分）在目标上相反，但状态设计和转移有相似之处，需要巧妙设计。

解题思路

这个问题是区间DP的经典难题。直接定义 dp[i][j] 为移除区间 [i, j] 内所有方块的最小成本，并不能很好处理“中间有同色块可合并”的情况。因为如果区间内两端方块颜色相同，你可能希望先处理中间的方块，让两端的同色块相邻后再合并，以获得更大的合并数量（从而单次成本更高，但总成本可能更低？注意这里是成本=数量的平方，我们希望成本最小，所以反而希望单次合并的数量尽量小？不一定，因为合并次数也会影响）。

实际上，在最小成本目标下，我们希望尽量以较小的块进行合并，因为成本是数量的平方，合并大块的成本增长很快。但合并次数增多也可能增加成本。因此需要动态规划权衡。

一种常见思路是定义状态 dp[i][j][k]，其中 k 表示在区间 [i, j] 的左边，有 k 个与 boxes[i] 颜色相同的方块，它们紧邻在区间 i 的左侧（可以看作已经合并好的、颜色为 boxes[i] 的块的数量）。这样，我们可以考虑两种策略：

1. 直接将 i 和左边的 k 个同色块一起合并掉，然后处理剩下的区间。
2. 在区间内找一个位置 m，使得 boxes[m] 的颜色与 boxes[i] 相同，先处理 [i+1, m-1] 这个子区间，让 i 和 m 及左边的 k 个块能连在一起，再处理剩下的部分。

这个状态定义和转移方程，其实和“移除盒子”（求最大得分）非常类似，只是目标改为最小成本。但在“移除盒子”中，得分是数量的平方，我们求最大得分；这里成本是数量的平方，我们求最小成本，所以目标函数形式相同，但优化方向相反。因此，我们可以沿用“移除盒子”的状态定义，但将“求最大得分”改为“求最小成本”，并相应调整转移方程。

状态定义

设 dp[i][j][k] 表示：考虑区间 [i, j] 内的方块，且在区间 i 的左边，有 k 个颜色与 boxes[i] 相同的方块（这些方块已经准备好可以与 boxes[i] 合并），将区间 [i, j] 以及这左边的 k 个同色方块全部移除（或合并）所需的最小成本。

初始时，对于整个区间 [0, n-1]，左边没有额外的同色方块，所以 k=0，答案就是 dp[0][n-1][0]。

状态转移

我们考虑如何移除位置 i 的方块（及其左边 k 个同色块）：

1. 策略1：直接将 i 和左边的 k 个同色块一起合并掉。那么这一次合并的块数是 (1+k)，成本为 (1+k)^2。然后，我们只需要处理剩下的区间 [i+1, j]，并且对于区间 [i+1, j] 来说，它的左边没有额外的同色块（因为 i 和左边的 k 个都合并移除了），所以后续成本是 dp[i+1][j][0]。因此，这种策略的总成本为：(1+k)^2 + dp[i+1][j][0]。

2. 策略2：我们不急于合并 i 和左边的 k 个块，而是先在区间 [i+1, j] 中找到一个位置 m，使得 boxes[m] 的颜色与 boxes[i] 相同。那么，我们可以先处理子区间 [i+1, m-1]，将这个子区间内的所有方块移除，使得 i 和 m 相邻。处理完 [i+1, m-1] 后，i 的右边紧邻着 m，而且它们颜色相同。此时，我们可以将 i、m 以及左边的 k 个同色块视为一组，但注意，此时 m 还在区间内，所以我们把 m 和它右边可能连着的同色块一起考虑进左边的计数。更准确地说，我们处理完 [i+1, m-1] 后，位置 i 和 m 相邻，颜色相同，那么我们可以将状态转化为：考虑区间 [m, j]，并且左边有 (k+1) 个与 boxes[m] 同色的方块（因为原来的 k 个加上位置 i 的这一个）。但注意，boxes[m] 本身还在区间内，所以我们需要在状态中表示“左边有额外同色块”时，这个 boxes[m] 本身不算在左边计数中。实际上，标准的“移除盒子”状态转移是：
   先移除 [i+1, m-1]，成本为 dp[i+1][m-1][0]。
   然后，剩下的区间是 [m, j]，并且此时位置 i 的方块（颜色同 boxes[m]）可以看作是在 boxes[m] 左边新增的一个同色块，所以对于区间 [m, j]，其左边同色块数量为 (k+1)。那么移除这部分的总成本是 dp[m][j][k+1]。
   因此，这种策略的总成本为：dp[i+1][m-1][0] + dp[m][j][k+1]。

我们需要遍历所有满足 i < m <= j 且 boxes[m] == boxes[i] 的位置 m，取上述两种策略的最小值。

边界条件

• 当 i > j 时，区间为空，移除成本为 0。
• 当 i == j 时，区间只有一个方块，此时移除它（和左边的 k 个同色块一起）的成本为 (1+k)^2。因为只需要一次合并，合并块数为 1+k。

状态转移方程

综合上述两种策略，我们有：

dp[i][j][k] = min(
    (1+k)^2 + dp[i+1][j][0],
    min_{m: i < m <= j, boxes[m] == boxes[i]} ( dp[i+1][m-1][0] + dp[m][j][k+1] )
)

其中，如果 i > j，则 dp[i][j][k] = 0。

计算顺序

由于状态 dp[i][j][k] 依赖于 dp[i+1][j][0]、dp[i+1][m-1][0] 和 dp[m][j][k+1]，其中 m > i，k 可以增大，所以我们需要按照区间长度从小到大的顺序计算，且对每个区间，k 从大到小计算（因为 k+1 比 k 大）。

时间复杂度

状态数：O(n^2 * n) 因为 k 最大为 n（极端情况下所有方块同色，左边同色块数量最多为 n）。但实际上我们可以限制 k 最大为 n，总状态数 O(n^3)。每个状态转移需要遍历 m，最坏 O(n)，总复杂度 O(n^4) 可能较高。但可以进行优化：因为 m 只在颜色相同的位置才有效，所以对于每个 i，可以预处理出所有同色位置，这样每个状态的转移均摊 O(同色位置数)，总体可优化到接近 O(n^3)。

示例详解

以 s = "aaabbbaa" 为例，颜色用字符表示，我们将其映射为数字，比如 'a'->1, 'b'->2。序列为 [1,1,1,2,2,2,1,1]。

我们计算 dp[0][7][0]。

计算过程（简略）：

• 区间长度从 1 开始计算单个方块的 dp[i][i][k] = (1+k)^2。
• 然后区间长度逐渐增大。
• 最终 dp[0][7][0] 会考虑各种分割点，得到最小成本。

实际上，对于这个序列，最优策略可能是：

1. 先合并中间三个 'b'（位置3~5），成本=9，序列变为三个块：[1,1,1] 和 [BBB] 和 [1,1]。
2. 此时，左边的三个 'a' 和右边的两个 'a' 被 'BBB' 隔开。我们需要将 'BBB' 移除，才能让两边的 'a' 相邻。移除 'BBB' 的成本已计为9。
3. 移除 'BBB' 后，序列变为五个 'a' 连续，此时合并这五个 'a'，成本=25。
   总成本 = 9 + 25 = 34。

但如果我们用另一种顺序：

1. 先合并前三个 'a'，成本=9，序列变为 [AAA,2,2,2,1,1]。
2. 合并后两个 'a'，成本=4，序列变为 [AAA,2,2,2,AA]。
3. 合并三个 'b'，成本=9，序列变为 [AAA,BBB,AA]。
4. 此时三个块颜色不同，必须再合并两次。例如先合并 AAA 和 AA？它们不同色，不能合并。所以我们必须逐个移除：比如先移除 AAA（成本=9），再移除 BBB（成本=9），再移除 AA（成本=4），总成本=9+4+9+9+4=35。可见不如上一种。

实际上，最优解可能是 34。这需要DP计算验证。

代码框架（伪代码）

def minCostToMergeBoxes(boxes):
    n = len(boxes)
    # 状态数组，初始化为较大值
    dp = [[[float('inf')] * (n+1) for _ in range(n)] for _ in range(n)]
    
    # 初始化：区间长度为1
    for i in range(n):
        for k in range(n+1):
            dp[i][i][k] = (1 + k) ** 2
    
    # 按区间长度从小到大计算
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            for k in range(n+1):
                # 策略1：直接合并i和左边的k个
                cost1 = (1+k)**2 + (dp[i+1][j][0] if i+1 <= j else 0)
                # 策略2：在[i+1, j]中找同色位置m
                min_cost = cost1
                for m in range(i+1, j+1):
                    if boxes[m] == boxes[i]:
                        # 注意子区间可能为空的情况
                        left_cost = dp[i+1][m-1][0] if i+1 <= m-1 else 0
                        right_cost = dp[m][j][k+1] if m <= j else 0
                        total = left_cost + right_cost
                        if total < min_cost:
                            min_cost = total
                dp[i][j][k] = min_cost
    return dp[0][n-1][0]

优化

• 可以预处理每个位置 i 右边下一个同色位置，加速策略2的查找。
• 可以用记忆化搜索实现，代码更简洁。

总结

这道题是区间DP中状态设计比较巧妙的一类问题，通过增加一维状态 k 来记录左边同色块的数量，从而能够处理“延迟合并以让同色块相邻”的情况。虽然目标是最小化合并成本（平方和），但状态转移与“移除盒子”求最大得分非常相似，只是将 max 改为 min，并注意成本计算即可。