0546. Remove Boxes
==================
题目信息
--------
:题号: 0546
:难度: Hard
:主题: 连续同色盒子、删除顺序、区间状态、最大得分
:原题: `LeetCode 0546 `_
:重点: 每次只能删除一段连续同色盒子、删除 k 个获得 k² 分、剩余部分拼接后可能形成新的同色连续段
题目重述
--------
给定整数数组 ``boxes``,每个整数表示一个盒子的颜色。一次操作可以选择当前数组中一段连续且颜色相同的 ``k`` 个盒子,将它们全部删除,并获得 ``k * k`` 分。
删除后,原来位于该段左右两侧的剩余盒子会直接相邻,可能形成新的同色连续段。可以自行决定每次删除顺序,返回删除全部盒子能够获得的最大总分。
自建示例
--------
先删除中间段可以合并两端:
.. code-block:: text
输入:boxes = [1,2,2,1]
输出:8
解释:先删除两个 2 得 4 分,剩余两个 1 变为连续,再删除得 4 分,总分为 8。
全部同色:
.. code-block:: text
输入:boxes = [3,3,3]
输出:9
解释:一次删除三个盒子可得 3²=9 分。
把可合并的同色盒子延迟处理
--------------------------
区间 ``[left,right]`` 之外已有 ``extra`` 个与 ``boxes[right]`` 同色的盒子紧贴在右侧时,若先删除 ``right``,只能得到 ``(extra+1)^2``;若把它和左侧同色盒子合并后再删除,可能获得更高分。因此状态定义为 ``dfs(left,right,extra)``,表示区间内盒子加上右侧额外同色盒子的最大得分。
先把 ``right`` 向左合并连续同色尾部,再考虑两种选择:立即删除这组盒子,或保留它,先删除中间部分以便与更左的同色盒子合并。
C++ 实现
--------
.. code-block:: cpp
class Solution {
std::vector boxes;
std::vector>> memo;
int search(int left, int right, int extra) {
if (left > right) return 0;
while (right > left && boxes[right] == boxes[right - 1]) {
--right;
++extra;
}
int& cached = memo[left][right][extra];
if (cached != -1) return cached;
cached = (extra + 1) * (extra + 1) +
search(left, right - 1, 0);
for (int middle = left; middle < right; ++middle) {
if (boxes[middle] != boxes[right]) continue;
cached = std::max(
cached,
search(left, middle, extra + 1) +
search(middle + 1, right - 1, 0));
}
return cached;
}
public:
int removeBoxes(std::vector& boxesValue) {
boxes = boxesValue;
int n = static_cast(boxes.size());
memo.assign(n, std::vector>(
n, std::vector(n + 1, -1)));
return search(0, n - 1, 0);
}
};
代码分析
--------
``extra`` 记录了跨过已删除区间后仍可合并的同色数量,因而每个状态包含决定未来得分的全部信息;立即删除和延迟合并覆盖所有可能的最优顺序。状态数为 ``O(n^3)``,每个状态还可能枚举合并位置,时间复杂度上界为 ``O(n^4)``,空间复杂度为 ``O(n^3)``。