题目链接：https://leetcode-cn.com/problems/remove-boxes/
参考链接：
给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。 当你将所有盒子都去掉之后，求你能获得的最大积分和。
示例 :
输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)
提示：
1 <= boxes.length <= 1001 <= boxes[i] <= 100
- 首先明确一点，可以通过递归完成这个过程，即按从头开始按序消除重复数字，然后剩下的数组继续按序消除，一次深度优先遍历过程，获取到所有结果，然后求出最大值
- 比如，第一次消除，可以是第一个重复，也可以是第二个重复，然后每个重复剩下的数组又可以继续这个过程，然后结果就是此次消除的值加上剩余数组消除值的最大值
- 但是这个方法会超时
- 这个思路也没有办法做记忆化，因为每次移除都会对子序列造成影响，导致结果不同
const removeBoxes = (boxes) => {
const getMax = (curBoxes, curSum) => {
let max = 0;
if (curBoxes.length == 0) return curSum;
if (curBoxes.length == 1) return curSum + 1 * 1;
let i = 0;
while (i < curBoxes.length) {
let count = 1; // 连续数字的个数
let j = i;
while (curBoxes[j + 1] == curBoxes[j]) {
count++;
j++;
}
const left = curBoxes.slice(0, i); // 左区间 最开始是空数组
const right = curBoxes.slice(j + 1); // 右区间
const curMax = getMax(left.concat(right), curSum + count * count);
max = Math.max(max, curMax); // 当前的划分情况下的curMax，挑战max
i = j + 1; // 或i=i+count，是等价的，就是不移除count这部分，i指针跳过它
}
return max;
};
return getMax(boxes, 0);
};- 与思路一类似，但是改变了处理顺序，添加了一个参数使其可以记忆化
- 然后我们将整个过程分为两部分
- 先消除这个连续数字，那么，这次结果就是
消除连续数字的贡献值 + 后面剩余数组的贡献值 - 先不消除，看后面有没有和这个数字相同的，消除两个数字中间的元素，加大这个连续数字的贡献，同时这次的结果就是
消除中间的元素的贡献值 + 剩余数组的贡献值(这个剩余数组就是前面带有连续数字的数组)
- 先消除这个连续数字，那么，这次结果就是
- 这样就可以将消除
[l,r]数组后，产生了多少连续数字，这个过程缓存起来 - 这个过程中是对每个序列进行递归，所以一定会产生重复移除
- 虽然每次移动之后的数组是不同的，无法记忆化，但是，移除之后的会对总积分产生贡献的序列是相同的，移除之后前缀产生了几个连续数字，如果贡献度相同就不需要重复计算，直接移除就好
/**
* @param {number[]} boxes
* @return {number}
*/
const removeBoxes = (boxes) => {
const n = boxes.length;
// js创建三维数组有点麻烦
const memo = new Array(n);
for (let i = 0; i < n; i++) {
memo[i] = new Array(n);
for (let j = 0; j < n; j++) {
memo[i][j] = new Array(n).fill(0);
}
}
// 函数定义：移除区间[l,r]和区间前面和boxes[l]相同的k个数，所能产出的最大积分和
const getMax = (l, r, k) => {
if (l > r) return 0;
if (memo[l][r][k] != 0) return memo[l][r][k];
// 找出连续的数字，有k+1个
while (l < r && boxes[l] == boxes[l + 1]) {
k++;
l++;
}
// 直接把这段连续的移除，收益(k+1)*(k+1)，加上对剩余部分的递归
let points = (k + 1) * (k + 1) + getMax(l + 1, r, 0)
// 移除中间部分子数组，让连续数字遇上和自己相同的数字
for (let i = l + 1; i <= r; i++) {
if (boxes[l] == boxes[i]) {
points = Math.max(
points,
getMax(l + 1, i - 1, 0) + getMax(i, r, k + 1)
)
}
}
memo[l][r][k] = points;
return points;
};
return getMax(0, n - 1, 0);
};