移除盒子（Remove Boxes）

题目描述
你面前有一排盒子，每个盒子有一种颜色，用一个整数数组 boxes 表示，其中 boxes[i] 是第 i 个盒子的颜色。你的目标是移除所有盒子。每次操作，你可以选择一段连续的、颜色相同的盒子（即 boxes[i] = boxes[j] 对区间内所有下标成立），然后将这段盒子移除。但移除操作后，如果这段盒子的左侧和右侧的盒子相邻，则它们会“接合”在一起，形成一个新序列。每次移除一段长度为 k 的相同颜色盒子，你将获得 k * k 的分数。请计算移除所有盒子所能获得的最高总分数。

示例
输入：boxes = [1,3,2,2,2,3,1,1]
可能的移除顺序：

1. 移除中间三个颜色为2的盒子：得分 3×3 = 9，序列变为 [1,3,3,1,1]
2. 移除中间两个颜色为3的盒子：得分 2×2 = 4，序列变为 [1,1,1]
3. 移除最后三个颜色为1的盒子：得分 3×3 = 9，总分为 9+4+9 = 22
   但存在更高得分的方案，比如先移除中间三个2，再移除旁边的3，然后剩下的1合并后再移除，可得更高分。
   你需要找到最优的移除顺序，使得总分最大。

解题思路
这是一个经典的“移除类”区间动态规划问题。其难点在于，当移除中间一段后，两侧的盒子可能会合并，如果它们颜色相同，就能在后续一次性移除获得更高分。因此，我们不能简单地只考虑一个区间 [l, r]，还需要记录这个区间右侧有多少个与 boxes[r] 颜色相同的盒子（这些盒子可能原本不相邻，但中间部分被移除后它们就能连起来）。这就引出了三维DP的定义。

1. 定义状态
设 dp[l][r][k] 表示在子数组 boxes[l..r] 的右侧，还有 k 个与 boxes[r] 颜色相同的盒子（这 k 个盒子是原本就在 r 的右侧，但可能因为在更右侧的区间中被先移除而暂时不考虑），在移除这个“扩展区间”时能获得的最大分数。
这里的“扩展区间”是指：boxes[l..r] 再加上它右侧那 k 个颜色同 boxes[r] 的盒子（这 k 个盒子是虚拟的，它们的位置在 r+1, r+2, ...，但可能中间有其他颜色的盒子被先移除了）。
之所以要这样定义，是因为当我们决定“将某个区间内所有与 boxes[r] 颜色相同的盒子一起移除”时，我们需要知道右侧有多少个相同颜色的盒子可以连起来一起移除，从而获得 (len + k)^2 的高分。

2. 状态转移
我们考虑如何计算 dp[l][r][k]。

• 策略1：直接将 boxes[r] 和它右侧那 k 个相同颜色的盒子一起移除。
  此时，我们先将 boxes[l..r-1] 这个区间全部移除（并假设在移除过程中，右侧那 k 个盒子还挂着），然后再将最后一段长度为 (1 + k) 的相同颜色盒子一起移除。
  所以得分是：dp[l][r-1][0] + (1 + k)*(1 + k)。
  这里 dp[l][r-1][0] 表示先把 [l, r-1] 区间全部移除（右侧没有额外相同颜色的盒子挂着）能得到的最高分。

• 策略2：在 [l, r-1] 区间内找一个位置 i，使得 boxes[i] 的颜色与 boxes[r] 相同。然后我们考虑将 boxes[i+1..r-1] 这段先移除，这样 boxes[i] 和 boxes[r] 就能连在一起（中间部分被移除了），此时右侧仍然有 k 个同色盒子连着，所以我们可以一起考虑。
  具体步骤：

  1. 将 boxes[i+1..r-1] 这个区间全部移除，此时 boxes[i] 和 boxes[r] 相邻，并且右侧还挂着 k 个同色盒子。
     这部分得分是 dp[i+1][r-1][0]。
  2. 此时，我们剩下的区间是 boxes[l..i] 再加上右侧那 (1 + 1 + k) 个同色盒子（其中 1 是 boxes[i] 自己，另一个 1 是 boxes[r]，再加上原来的 k 个）。
     所以接下来我们需要计算 dp[l][i][k+1] 的最大得分。
     总得分是：dp[i+1][r-1][0] + dp[l][i][k+1]。
     我们要遍历所有 i ∈ [l, r-1] 且 boxes[i] == boxes[r]，取最大值。

因此状态转移方程为：

dp[l][r][k] = max(
    dp[l][r-1][0] + (1 + k)^2,
    max_{i=l..r-1, boxes[i]==boxes[r]} (dp[i+1][r-1][0] + dp[l][i][k+1])
)

其中，如果找不到这样的 i，则只有第一种策略。

3. 边界条件

• 当 l > r 时，区间为空，得分为 0。
• 当 l == r 时，只有一个盒子，此时 dp[l][r][k] = (1 + k)^2，因为我们可以将这个盒子和右侧 k 个同色盒子一起移除。

实际实现时，我们采用记忆化搜索（递归+备忘录）来避免复杂的循环顺序。

4. 计算顺序
因为状态 dp[l][r][k] 依赖于：

• dp[l][r-1][0]（区间更小）
• dp[i+1][r-1][0]（区间更小）
• dp[l][i][k+1]（k 变大，但区间更小）
  所以我们可以用递归函数 solve(l, r, k) 来计算，并用三维数组记忆化。

5. 最终答案
整个数组是 boxes[0..n-1]，初始时右侧没有额外的同色盒子，所以答案是 dp[0][n-1][0]。

6. 示例推演
以 boxes = [1,2,1] 为例（n=3），计算过程简述：

• 计算 dp[0][2][0]（即整个数组，右侧无额外盒子）
  • 策略1：先移除 [0,1] 区间，再移除最后一个盒子（颜色1）。但这样得分不一定最高。
  • 策略2：在 [0,1] 中找颜色同 boxes[2]=1 的位置，即 i=0。
    先移除 boxes[1]（颜色2），得分 1，然后剩下 [0] 和右侧额外 k+1=1 个同色盒子（即 boxes[2]），得分为 (1+1)^2=4，总分 1+4=5。
    而策略1的得分可能是：先移除中间的2，再移除两边的1，得分 1+4=5 相同。
    实际上最优是 5。

7. 时间复杂度
状态数为 O(n^2 * n) = O(n^3)（因为 k 最大为 n），每个状态需要遍历 O(n) 个可能的 i，所以总复杂度 O(n^4)。但通过优化（预处理相同颜色的位置，减少遍历），可降至 O(n^3)。在 n ≤ 100 时可行。

8. 代码框架（记忆化搜索）

def removeBoxes(boxes):
    n = len(boxes)
    memo = [[[0] * n for _ in range(n)] for __ in range(n)]

    def dp(l, r, k):
        if l > r:
            return 0
        if memo[l][r][k] > 0:
            return memo[l][r][k]
        # 压缩右侧相同的盒子
        while r > l and boxes[r] == boxes[r-1]:
            r -= 1
            k += 1
        # 策略1
        res = dp(l, r-1, 0) + (k + 1) * (k + 1)
        # 策略2
        for i in range(l, r):
            if boxes[i] == boxes[r]:
                res = max(res, dp(l, i, k+1) + dp(i+1, r-1, 0))
        memo[l][r][k] = res
        return res

    return dp(0, n-1, 0)

这里的“压缩”是优化：如果 boxes[r] 和前面几个颜色相同，我们直接合并到 k 中，减少区间长度。

9. 总结
本题的关键在于状态设计：dp[l][r][k] 表示区间 [l, r] 加上右侧 k 个同色盒子时的最大得分。通过考虑最后一段同色盒子何时移除（是直接与右侧 k 个一起移除，还是先合并中间的同色盒子再一起移除），可以构造出状态转移方程。这个思路是区间DP中处理“合并后产生新连接”的典型方法。