546. 移除盒子

发表于 2026-01-22 分类于力扣阅读次数： Waline：本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

区间DP

思路

1. 问题的本质（抛开“消除过程”）

给定一个颜色序列： \[ \text{boxes} = [c_1, c_2, \dots, c_n] \] 一次操作可以消除一段连续的同色盒子，若该段长度为 \(k\)，则得分为： \[ k^2 \] 消除后，左右两侧的盒子会拼接在一起，可能形成新的连续同色段。

1.1 关键困难

与普通“区间消除”问题不同，本题的核心困难在于：

同一个子区间，在不同“外部环境”下，其最优消除策略可能不同。

例如：

1 2	[1, 2, 1] → 最优是先消 2，再消 1,1 [1, 2, 1, 1] → 最优是先消 2，再把三个 1 一起消

也就是说：

[1,2,1] 单独看的最优策略
与 [1,2,1] 作为更大区间的一部分时的最优策略
是不一样的

👉 因此，仅用二维 f[l][r] 无法表达“是否要把当前颜色留给外部合并”这一信息。

2. 状态建模：为什么必须引入第三维

2.1 状态定义

定义三维 DP 状态： \[ f(i, j, r) \] 表示：

在区间 \([i, j]\) 内的盒子全部被消除，且认为第 \(j\) 个盒子的颜色在右侧已经额外合并了 \(r\) 个同色盒子，所能获得的最大分数。

其中：

\(i, j\) 为区间端点（闭区间）
\(r \ge 0\)
当前这“一团”同色盒子的实际大小为： \[ r + 1 \]

2.2 第三维 \(r\) 的本质含义

\(r\) 不是数组中真实存在的盒子数量，而是一个结构性信息：

它表示： 当前区间右端颜色已经被“承诺”要和外部的 \(r\) 个同色盒子合并成同一团

这使得 DP 能表达以下关键决策：

是现在就结算这一团同色盒子
还是继续保留，等待与区间左侧（或更外层）的同色盒子合并

3. 状态转移的完整推导

固定一个状态 \(f(i, j, r)\)，设当前右端颜色为： \[ c = \text{boxes}[j] \]

3.1 转移一：在当前位置结算这一团同色盒子

逻辑含义

不再尝试与区间左侧的同色盒子合并
当前同色团的大小为 \(r+1\)
先消除区间 \([i, j-1]\)，再一次性消除这 \(r+1\) 个盒子

数学表达

\[ f(i, j, r) \;\ge\; f(i, j-1, 0) + (r+1)^2 \]

解释

\(f(i, j-1, 0)\)：左侧区间独立消除
\((r+1)^2\)：当前同色团的得分

3.2 转移二：将右端盒子并入左侧某个同色位置

逻辑含义

在区间 \([i, j-1]\) 中寻找某个位置 \(k\)，满足： \[ \text{boxes}[k] = \text{boxes}[j] \]
先完全消除中间区间 \([k+1, j-1]\)
使得 \(k\) 与 \(j\)（及其右侧 \(r\) 个同色盒子）形成更大的同色团
将该团交由左侧区间 \([i, k]\) 继续处理

数学表达

\[ f(i, j, r) \;\ge\; \max_{\substack{i \le k < j \\ \text{boxes}[k] = \text{boxes}[j]}} \left( f(i, k, r+1) + f(k+1, j-1, 0) \right) \]

解释

\(f(k+1, j-1, 0)\)：必须完全清空中间区间
\(f(i, k, r+1)\)：右端同色团规模扩大 1，继续向左合并

4. 边界条件与答案

4.1 边界

当 \(i > j\) 时： \[ f(i, j, r) = 0 \]
当 \(i = j\) 时： \[ f(i, i, r) = (r+1)^2 \]

4.2 最终答案

\[ \boxed{f(1, n, 0)} \]

表示：整个数组消除完毕，且最右端没有外部同色盒子参与合并。

5. 复杂度分析

状态数量：\(O(n^3)\)
每个状态枚举 \(k\)：\(O(n)\)
总时间复杂度：\(\boxed{O(n^4)}\)
空间复杂度：\(\boxed{O(n^3)}\)

这是一个典型的高维区间 DP，复杂但结构完全清晰。

6. AC代码

6.1 记忆化搜索版本（DFS）

class Solution {
public:
    vector<int> arr;
    int f[105][105][105];

    // f(i, j, r):
    // 消除区间 [i, j]，并假设 boxes[j] 右侧已经有 r 个同色盒子合并
    int dfs(int i, int j, int r) {
        if (i > j)
            return 0;

        int& res = f[i][j][r];
        if (res != -1)
            return res;

        // 转移一：在这里直接结算右端这一团
        res = dfs(i, j - 1, 0) + (r + 1) * (r + 1);

        // 转移二：尝试将 boxes[j] 并入左侧某个同色位置 k
        for (int k = j - 1; k >= i; --k) {
            if (arr[j - 1] == arr[k - 1]) {
                res = max(res,
                          dfs(i, k, r + 1) +
                          dfs(k + 1, j - 1, 0));
            }
        }
        return res;
    }

    int removeBoxes(vector<int>& boxes) {
        arr = boxes;
        memset(f, -1, sizeof(f));
        return dfs(1, arr.size(), 0);
    }
};

6.2 自底向上三维 DP 版本

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int f[105][105][105] = {};
        int n = boxes.size();

        // 初始化：单点区间
        for (int i = 1; i <= n; ++i) {
            for (int r = 0; r <= n; ++r) {
                f[i][i][r] = (r + 1) * (r + 1);
            }
        }

        // 按区间长度递增
        for (int len = 2; len <= n; ++len) {
            for (int j = len; j <= n; ++j) {
                int i = j - len + 1;
                for (int r = n; r >= 0; --r) {

                    // 转移一：直接结算右端
                    f[i][j][r] = f[i][j - 1][0] + (r + 1) * (r + 1);

                    // 转移二：枚举左侧同色位置 k
                    for (int k = j - 1; k >= i; --k) {
                        if (boxes[j - 1] == boxes[k - 1]) {
                            f[i][j][r] =
                                max(f[i][j][r],
                                    f[i][k][r + 1] +
                                    f[k + 1][j - 1][0]);
                        }
                    }
                }
            }
        }
        return f[1][n][0];
    }
};

7. 总结一句话

Remove Boxes 的本质不是“消除顺序”，而是“在区间约束下，如何对同色位置进行最优分组，使得平方和最大”。

第三维 \(r\) 的存在，正是为了表达这种跨区间、上下文相关的分组决策。