移除盒子问题（进阶版） 题目描述 给定一个整数数组 boxes，其中 boxes[ i] 表示第 i 个盒子的颜色。每次操作，你可以移除一些连续的同色盒子，每次移除可以获得 k * k 的分数，其中 k 是本次移除的盒子数量。重复这个过程，直到所有盒子都被移除。计算你能获得的最大分数。 例如： 输入：boxes = [ 1, 3, 2, 2, 2, 3, 4, 3, 1 ] 输出：23 解释： [ 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[ l][ r] 定义（表示移除区间 [ l, r ] 的最大得分）无法处理这种合并情况。 状态设计 我们需要一个更强大的状态表示来记录“合并潜力”。定义 dp[ l][ r][ k] 为：在区间 [ l, r] 的右边，还有 k 个与 boxes[ r] 颜色相同的盒子“附着”在 r 的右侧（这些盒子在原始序列中可能与 r 不相邻，但通过移除中间的其他盒子后，它们变得与 r 相邻），那么通过移除这整个“大块”（即区间 [ l, r ] 加上右边附着的 k 个同色盒子）所能获得的最大分数。 l , r 定义区间的左右端点。 k 表示在区间 [ l, r] 的右侧，还有 k 个颜色与 boxes[ r] 相同的盒子。这些盒子在原始序列中可能不在区间 [ l, r ] 内，但在我们考虑移除顺序时，它们最终会与 r 处的盒子合并。 状态转移方程 我们考虑如何计算 dp[ l][ r][ k ]。 策略1：直接移除末尾的连续同色块 我们可以选择直接将区间 [ l, r] 以及右边附着的 k 个同色盒子一起移除。这个同色块的总长度是 (在区间 [ l, r] 中，从 r 开始向左连续与 boxes[ r] 同色的盒子数量) + k。我们记这个连续同色段的长度为 len 。 那么这种策略的得分是： dp[l][r][k] = dp[l][r-1][0] + (len + k) * (len + k) （解释：先最优地移除区间 [ l, r-1] 并且右边不附着任何盒子，得分 dp[ l][ r-1][ 0 ]，然后一次性移除最后这个长度为 (len+k) 的大同色块。） 策略2：将区间分割，让中间的同色部分与末尾合并 我们可以在区间 [ l, r] 内部寻找一个位置 i，使得 boxes[ i] 的颜色与 boxes[ r ] 的颜色相同。这样，我们可以将问题分解： 先处理区间 [ l, i] 和区间 [ i+1, r-1]。注意，当我们处理区间 [ i+1, r-1 ] 时，我们希望 r 处的盒子（以及右边附着的 k 个盒子）能保留下来，以便之后与 i 处的盒子合并。 具体来说，我们可以将状态定义为： dp[l][r][k] = max(dp[l][r][k], dp[l][i][k + (从r开始向左连续同色长度)] + dp[i+1][r-1][0]) 更精确的递推式：我们遍历区间 [ l, r-1] 内的所有位置 i，使得 boxes[ i] == boxes[ r ]。 那么： dp[l][r][k] = max(dp[l][r][k], dp[l][i][k + len_r] + dp[i+1][r-1][0]) 其中 len_r 是从 r 开始向左连续与 boxes[ r] 同色的盒子数量（不包括 i 本身，且这些盒子必须在 [ i+1, r-1] 区间内）。实际上， len_r 的计算可以简化：当我们找到 i 时，我们可以认为我们将区间分成了 [ l, i] 和 [ i+1, r-1] 两部分。对于 [ l, i ] 部分，我们让它右边附着的盒子数变为 (k + 从r开始向左连续同色直到i+1的长度)。而这个长度，可以通过预处理，或者更简单地，在递归或迭代时，通过一个变量来记录。 在实际实现中，我们通常采用记忆化搜索（递归+缓存）的方式，因为递推的顺序不太直观。我们定义一个递归函数 solve(l, r, k) ，表示计算 dp[ l][ r][ k ]。 递归基 ：如果 l > r，区间为空，得分为0。 算法步骤（记忆化搜索） a. 预处理（可选）：为了快速找到与 boxes[ r ] 相同颜色的位置，可以提前记录，但通常直接遍历即可。 b. 定义递归函数 solve(l, r, k) ： * 如果 l > r: 返回 0。 * 如果 l == r: 直接移除这一个盒子加上右边的 k 个同色盒子，得分 (1+k) (1+k)。 否则： 1. 优化 ：如果 boxes[ r] == boxes[ r-1]，我们可以先“收缩”区间，避免重复计算。即： solve(l, r, k) = solve(l, r-1, k+1) 。因为此时 r 和 r-1 同色，我们可以认为在状态中，r 这个盒子已经被合并到了右边的附着块中（k增加了1），然后我们计算区间 [ l, r-1 ] 附着着 k+1 个盒子的最大得分。这等价于直接处理一个更短的区间。 2. 如果不满足上述优化条件，或者我们想显式地计算所有情况： * 初始化得分： score = solve(l, r-1, 0) + (1+k)*(1+k) （策略1） * 遍历 i 从 l 到 r-1： * 如果 boxes[ i] == boxes[ r ]： * score = max(score, solve(l, i, k+1) + solve(i+1, r-1, 0)) （解释：将区间分为 [ l, i] 和 [ i+1, r-1]。对于 [ l, i]，我们让它最终与 r 处的盒子以及右边的 k 个盒子合并，所以它右边附着的盒子数是 k+1（这个1就是 r 处的盒子）。而对于区间 [ i+1, r-1 ]，我们独立地、最优地移除它，并且移除后右边不附着任何盒子。） c. 返回 score 。 c. 最终答案就是 solve(0, n-1, 0) ，其中 n 是 boxes 的长度。 复杂度分析 状态数：O(n² * n) = O(n³)，因为 l 和 r 各有 O(n) 种，k 最大可能为 n（极端情况整个数组同色）。 每个状态的计算需要遍历 O(n) 个分割点 i。 总时间复杂度为 O(n⁴)。这看起来很高，但通过上述的“收缩”优化（当 boxes[ r] == boxes[ r-1 ] 时直接递归到 solve(l, r-1, k+1)），可以避免大量重复计算，实际上跑得很快。在 LeetCode 上可以接受。 空间复杂度：O(n³)，用于存储记忆化搜索的结果。 示例演示（简要） 以 boxes = [ 1, 3, 2, 2, 2, 3, 4, 3, 1] 为例，计算 dp[ 0][ 8][ 0] 的过程非常复杂，但算法会正确地探索所有可能的移除顺序，包括先移除中间的 [ 2,2,2] 得9分，然后剩下的 [ 1,3,3,4,3,1 ] 中，3 和 3 变得相邻，可以合并移除再得高分，最终找到 23 这个最优解。 这个问题的核心在于状态设计中引入的第三个维度 k，它巧妙地刻画了“未来可能合并”的潜力，是解决这类“移除后会产生合并”问题的经典方法。