移除盒子问题

题目描述
给定一个整数数组 boxes，表示一排盒子，每个盒子的颜色由数字表示。每次操作可以移除连续相同颜色的 k 个盒子（k ≥ 1），并获得 k * k 分。求移除所有盒子能获得的最大分数。

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

1. 移除三个连续的 2（得 3×3=9 分）→ [1,3,3,4,3,1]
2. 移除一个 4（得 1×1=1 分）→ [1,3,3,3,1]
3. 移除三个连续的 3（得 3×3=9 分）→ [1,1]
4. 移除两个连续的 1（得 2×2=4 分）→ []
   总得分：9+1+9+4=23。

解题思路
此问题不能直接用常规区间 DP（如 dp[i][j] 表示移除区间 [i,j] 的最大得分）解决，因为移除中间某段后，两端的同色盒子可能合并，产生更高分数。需额外记录区间右侧与 boxes[j] 同色的盒子个数。

状态定义
dp[i][j][k] 表示在区间 [i,j] 中，在 j 之后还有 k 个与 boxes[j] 同色的盒子（这些盒子原本与 j 连续，但可能因中间移除操作而暂时分离）时，能获得的最大分数。

状态转移

1. 直接移除末尾段：将 j 及其右侧连续的 k+1 个同色盒子一起移除，得分为 (k+1)*(k+1) + dp[i][j-1][0]。
2. 在区间内寻找与 j 同色的位置 p，将区间分成三段：
   • [i, p-1]：移除后可能使 p 与 j 之间的盒子被清理，让 p 与 j 及右侧 k 个盒子连续。
   • [p+1, j-1]：中间段移除后，p 与 j 连接。
     转移方程：
     dp[i][j][k] = max(dp[i][j][k], dp[i][p][k+1] + dp[p+1][j-1][0])
     其中 boxes[p] == boxes[j] 且 i ≤ p < j。

初始化
区间长度为 0 时，dp[i][i-1][k] = 0。
单盒子区间 [i,i]：dp[i][i][k] = (k+1)*(k+1)。

计算顺序
按区间长度从小到大计算。

详细步骤
以 boxes = [1,3,2,2,2,3,4,3,1] 为例：

1. 初始化所有 dp[i][i][k] = (k+1)^2。
2. 长度 L=2：计算所有相邻区间，如 [0,1]（颜色 1,3）无同色，直接移除末尾得 (k+1)^2 + 另一区间分。
3. 逐步扩大区间，重点处理同色连接情况：
   • 当计算 [i,j] 时，遍历 p 从 i 到 j-1，若 boxes[p] == boxes[j]，则尝试合并 p 与 j 的连续段。
4. 最终结果：dp[0][n-1][0]。

代码框架（伪代码）

n = len(boxes)
dp = [[[0]*(n+1) for _ in range(n)] for _ in range(n)]

for i in range(n):
    for k in range(n):
        dp[i][i][k] = (k+1)*(k+1)

for L in range(2, n+1):
    for i in range(n-L+1):
        j = i+L-1
        for k in range(n):
            # 方案1：直接移除末尾段
            dp[i][j][k] = (k+1)**2 + dp[i][j-1][0]
            # 方案2：在区间内找同色点p
            for p in range(i, j):
                if boxes[p] == boxes[j]:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][p][k+1] + dp[p+1][j-1][0])

return dp[0][n-1][0]