区间动态规划例题：移除盒子问题 题目描述 给定一个整数数组 boxes ，其中不同的整数表示不同颜色的盒子。每次操作，你可以移除连续相同颜色的 k 个盒子（k ≥ 1），并获得 k * k 分。求最多能获得多少分。 示例 输入： boxes = [1,3,2,2,2,3,4,3,1] 输出： 23 解释： 移除顺序示例： 移除三个连续的 2（颜色 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][k] 表示在区间 [l, r] 中，在 r 右侧还有 k 个与 boxes[r] 颜色相同的盒子（这些盒子尚未被移除，且与 boxes[r] 连续）时，能获得的最大分数。 l 、 r 为区间左右端点（0 ≤ l ≤ r < n）。 k 表示在 r 右侧有 k 个与 boxes[r] 颜色相同的盒子（这些盒子原本可能在区间外或后续合并而来）。 状态转移 情况1 ：直接移除右侧连续段 移除 r 及其右侧的 k 个相同颜色盒子，得分 (k+1)^2 ，然后处理剩余区间 [l, r-1] ： dp[l][r][k] = dp[l][r-1][0] + (k+1)^2 情况2 ：在 [l, r-1] 中寻找与 r 颜色相同的位置 i ，先处理 [i+1, r-1] ，让 i 与 r 及右侧的 k 个盒子连续 若存在 i （l ≤ i < r）使得 boxes[i] == boxes[r] ，则： 将 [l, r] 分为三部分： [l, i] ：包含与 r 同色的盒子 i [i+1, r-1] ：中间区间（与 r 不同色） r 及其右侧 k 个同色盒子 先移除 [i+1, r-1] ，让 i 与 r 及右侧 k 个盒子连续，再一起处理： dp[l][r][k] = max(dp[l][r][k], dp[l][i][k+1] + dp[i+1][r-1][0]) 注意：这里 k+1 是因为 r 及其右侧的 k 个盒子会与 i 连接，形成更大的连续段。 初始化与计算顺序 初始化： dp[l][r][k] = 0 （区间长度为0时得分为0）。 按区间长度从小到大计算（区间长度 len 从 1 到 n）。 最终答案 dp[0][n-1][0] （整个区间右侧无额外盒子）。 示例推导（boxes = [ 1,3,2,2,2,3,4,3,1]） 初始化所有 dp[l][r][k] = 0 （当 l > r 时）。 计算区间长度 1 到 n： 例如区间 [2,4] （颜色 [2,2,2] ）： 直接移除： dp[2][4][0] = dp[2][3][0] + 1^2 ，递归计算后得 9。 最终计算 dp[0][8][0] 时，会考虑多种分割方案，通过状态转移找到最大值 23。 总结 关键点：定义 k 表示右侧连续同色盒子数量，允许后续合并获得更高分。 时间复杂度：O(n⁴)（三层循环区间 + 一层枚举分割点），但实际剪枝后可优化。 核心思想：通过保留某些同色盒子延迟移除，实现分数最大化。