区间动态规划例题：移除盒子问题（进阶版） 题目描述 给定一个整数数组 boxes ，其中 boxes[i] 表示第 i 个盒子的颜色。每次操作可以移除所有颜色相同的连续盒子，这样一次操作可以得分为 k * k ，其中 k 是移除的连续盒子数量。目标是找到通过一系列操作能获得的最大得分。 例如，对于输入 boxes = [1, 3, 2, 2, 2, 3, 4, 3, 1] ，一个最优移除顺序是： 移除三个连续的 2，得分为 3 * 3 = 9，剩下 [1, 3, 3, 4, 3, 1] 移除一个 4，得分为 1 * 1 = 1，剩下 [1, 3, 3, 3, 1] 移除三个连续的 3，得分为 3 * 3 = 9，剩下 [1, 1] 移除两个连续的 1，得分为 2 * 2 = 4 总得分为 9 + 1 + 9 + 4 = 23。 解题过程 这个问题的难点在于移除盒子后相邻盒子可能形成新的连续颜色块，因此需要动态规划来考虑所有可能的移除顺序。我们使用一个三维动态规划数组 dp[i][j][k] ，表示在区间 [i, j] 中，如果在该区间左侧有 k 个与 boxes[i] 颜色相同的盒子连续连接，通过移除这些盒子能获得的最大得分。 步骤分解 状态定义 dp[i][j][k] ：在子数组 boxes[i...j] 上，且在该区间之前有 k 个与 boxes[i] 颜色相同的盒子连续连接时，能获得的最大得分。 这里的 k 表示在区间开始前已经有多少个与 boxes[i] 颜色相同的盒子，这些盒子可以与区间内的同色盒子一起移除以获得更高的 k 值（从而获得更高的 k² 得分）。 基础情况 当 i > j 时，区间无效，得分为 0。 当 i = j 时，只有一个盒子，得分为 (k + 1) * (k + 1) ，因为当前盒子与前面的 k 个同色盒子一起移除。 状态转移方程 考虑区间 [i, j] 和附加的 k 个同色盒子： 策略1 ：直接移除前面的 k 个盒子和当前盒子 i ，然后处理剩下的区间 [i+1, j] ，此时附加的同色盒子数为 0。 得分 = (k + 1) * (k + 1) + dp[i+1][j][0] 策略2 ：在区间 [i+1, j] 中寻找与 boxes[i] 颜色相同的位置 m ，将问题分割为三部分： 区间 [i+1, m-1] ：处理中间不同色的部分，附加同色盒子数为 0。 区间 [m, j] ：处理剩余部分，此时附加的同色盒子数为 k + 1 （因为 boxes[i] 和 boxes[m] 颜色相同，且前面已有 k 个同色盒子）。 得分 = dp[i+1][m-1][0] + dp[m][j][k+1] 状态转移方程为两者取最大值： dp[i][j][k] = max( (k+1)^2 + dp[i+1][j][0], max_{m} { dp[i+1][m-1][0] + dp[m][j][k+1] } ) 其中 m 遍历所有 i+1 到 j 的位置，且满足 boxes[m] == boxes[i] 。 计算顺序 由于状态 dp[i][j][k] 依赖于 dp[i+1][...][...] 和 dp[m][j][k+1] ，我们需要按区间长度从小到大计算： 外层循环：区间长度 len 从 1 到 n 内层循环：区间起始点 i 从 0 到 n - len j = i + len - 1 内层循环 k 从 0 到 i（因为最多只能有 i 个盒子在区间之前） 最终答案 整个问题的解是 dp[0][n-1][0] ，即在完整区间 [0, n-1] 上，且前面没有附加同色盒子时的最大得分。 示例计算 以 boxes = [1, 3, 2, 2, 2, 3, 4, 3, 1] 为例： 初始化所有 dp[i][j][k] 为 0 计算长度为 1 的区间： dp[i][i][k] = (k + 1)^2 逐步计算更长的区间，考虑所有可能的分割点 最终 dp[0][8][0] = 23 这个算法的时间复杂度是 O(n⁴)，空间复杂度是 O(n³)，在 n ≤ 100 时是可接受的。