移除盒子（Remove Boxes）

题目描述

给你一个由整数组成的数组 boxes，其中 boxes[i] 表示第 i 个盒子的颜色。你可以进行如下操作：每次选择连续的、颜色相同的一段盒子，并将它们全部移除，从而获得得分。得分的计算方式为：移除的盒子数量 × 移除的盒子数量（即 k × k，其中 k 是这段连续盒子的长度）。

你可以任意次数地进行移除操作，直到所有盒子被移完为止。要求返回可以获得的最大总分数。

示例

输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
一种最优移除顺序为：

1. 移除 [2,2,2]，得分 = 3×3 = 9，剩下 [1,3,3,4,3,1]
2. 移除 [3,3]，得分 = 2×2 = 4，剩下 [1,4,3,1]
3. 移除 [1]，得分 = 1×1 = 1，剩下 [4,3,1]
4. 移除 [4]，得分 = 1×1 = 1，剩下 [3,1]
5. 移除 [3]，得分 = 1×1 = 1，剩下 [1]
6. 移除 [1]，得分 = 1×1 = 1
   总得分 = 9+4+1+1+1+1 = 17（这不是最优，实际上有更高分 23 的策略，比如先合并远处的相同颜色）。

实际上，一种得到 23 分的策略是：

1. 移除 [3]（第 2 个位置），得 1 分 → [1,2,2,2,3,4,3,1]
2. 移除 [4]，得 1 分 → [1,2,2,2,3,3,1]
3. 移除 [2,2,2]，得 9 分 → [1,3,3,1]
4. 移除 [1]（第一个），得 1 分 → [3,3,1]
5. 移除 [3,3]，得 4 分 → [1]
6. 移除 [1]，得 1 分
   总 17 分仍不对，说明需要更优的顺序。实际上最优 23 分的策略涉及将远处同色的盒子保留，直到中间其他盒子被消除，使它们连成更长的段，这正是本题的难点。

解题思路详解

这个问题之所以困难，是因为普通的区间 DP 如 dp[i][j] 表示区间 [i,j] 的最大得分不够用。原因在于：移除中间某段后，两边的同色盒子可能会在后续中连接起来，从而形成更长的连续段，获得更高分。

状态定义

定义 dp[i][j][k]：

• 表示在区间 [i, j] 上，在区间 i 的左侧有 k 个连续的颜色与 boxes[i] 相同的盒子（这些盒子是之前尚未被移除的，并且和 boxes[i] 颜色相同，可以视为“附着”在区间左端）。
• 这个状态的得分，是将这些左侧的 k 个盒子与区间内可能与它们同色的盒子合并移除能获得的最大得分，加上区间内其他部分的得分。

为什么需要 k 这个维度？
因为当我们考虑消除 boxes[i] 时，如果它和左边的盒子颜色相同，我们可以不立即消除它们，而是等到后面某个同色的位置，一起消除，以获取更大的 k' 值（从而得到 k'×k' 的高分）。

状态转移

考虑区间 [i, j] 和左侧附加的 k 个同色盒子（颜色同 boxes[i]）。

1. 直接消除左侧 k 个盒子和 boxes[i] 及其之后的一些连续同色盒子：
   可以先消除 boxes[i] 以及右边与它同色的连续段（假设从 i 到 p 颜色相同），那么得分是 (k + len)^2，然后加上 dp[p+1][j][0]。
   但这种方法在 DP 中不是唯一策略，更好的方式是“推迟”消除，让更远的同色盒子也合并进来。

2. 更好的策略：
   我们不急于消除 boxes[i]，而是在区间 [i, j] 中寻找另一个位置 m，使得 boxes[m] == boxes[i]，这样我们可以把区间分成三部分：

   • 第一部分：[i+1, m-1]，先消除这部分，让 i 和 m 相邻。
   • 第二部分：此时 i 和 m 颜色相同，且左侧还连着 k 个同色盒子，所以当我们考虑区间 [m, j] 时，左侧附加的同色盒子数变为 k + 1（因为 i 与 m 同色，且 i 在左侧）。
   • 第三部分：[m, j] 区间在左侧有 k+1 个同色盒子的情况。

   于是转移方程为：

   dp[i][j][k] = max( 
        (k+1)^2 + dp[i+1][j][0],   // 策略1：直接消除 i 和左边 k 个盒子
        max_{m} ( dp[i+1][m-1][0] + dp[m][j][k+1] )  // 策略2：m 是 i 右边第一个 boxes[m]==boxes[i] 的位置
   )
   

   但注意，m 不一定是第一个相同颜色的位置，可以是任意相同颜色的位置。我们需要枚举所有这样的 m。

   实际更准确的转移：

   • 如果直接消除 i 及左边 k 个：dp[i][j][k] = (k+1)*(k+1) + dp[i+1][j][0]。
   • 否则，在 [i+1, j] 中找一个位置 m 使得 boxes[m] == boxes[i]，然后：

     dp[i][j][k] = max( dp[i][j][k], dp[i+1][m-1][0] + dp[m][j][k+1] )
     

     这里 dp[i+1][m-1][0] 表示先独立消除 i+1 到 m-1 之间的盒子，然后剩下的区间 [m, j] 在它的左侧有 k+1 个同色盒子（因为 boxes[i] 颜色同 boxes[m]，且左边 k 个同色盒子加上 i 本身，共 k+1 个“挂”在 m 左侧）。

边界条件

• 当 i > j 时，区间为空，得分为 0。
• 当 i == j 时，区间只有一个盒子，得分为 (k+1)^2（因为左侧有 k 个同色盒子，加上这个盒子共 k+1 个一起消除）。

计算顺序

区间 DP 一般按区间长度从小到大计算。
但这里因为有第三维 k，而且 k 最大可能为区间长度（如果整个区间颜色相同），所以 k 维度也需考虑。不过，k 实际上在计算中不会超过剩余的同色盒子数，可以在递推时动态决定。
实现时用记忆化搜索更自然。

最终答案

答案是 dp[0][n-1][0]，即在区间 [0, n-1] 上，左侧没有附加的盒子时的最大得分。

示例推导（简要）

输入：[1,3,2,2,2,3,4,3,1]，n=9。
我们用记忆化搜索来理解：

dp(0,8,0)：

• i=0, boxes[0]=1, 在右边找 m 使得 boxes[m]==1，找到 m=8。
  则转移考虑两种：
  1. 直接消除 i：得分 1 + dp(1,8,0)
  2. 利用 m=8：先消去 [1,7]，得到 dp(1,7,0)，然后剩下区间 [8,8] 左侧有 1 个同色盒子（因为 i=0 颜色为 1，附加到 m=8），即 dp(8,8,1) = (1+1)^2=4。
     所以总分为 dp(1,7,0) + 4。

我们需要递归计算 dp(1,7,0) 等，最终得到最大值 23。

实现细节（记忆化搜索）

def removeBoxes(boxes):
    n = len(boxes)
    memo = [[[0]*n for _ in range(n)] for _ in range(n)]
    
    def dfs(i, j, k):
        if i > j:
            return 0
        if memo[i][j][k] != 0:
            return memo[i][j][k]
        # 合并连续同色的
        while i+1 <= j and boxes[i+1] == boxes[i]:
            i += 1
            k += 1
        # 情况1：直接消除
        res = (k+1)*(k+1) + dfs(i+1, j, 0)
        # 情况2：找后面的同色位置合并
        for m in range(i+1, j+1):
            if boxes[m] == boxes[i]:
                res = max(res, dfs(i+1, m-1, 0) + dfs(m, j, k+1))
        memo[i][j][k] = res
        return res
    
    return dfs(0, n-1, 0)

总结

移除盒子问题是一个经典的三维区间DP问题，核心难点在于状态设计中要记录左侧附加的同色盒子数 k，以处理“延迟合并”带来的更高收益。
通过记忆化搜索，按上述转移方程递归求解，可得到最大得分。时间复杂度 O(n^4) 在优化后（如合并连续同色）可降低，空间复杂度 O(n^3)。