天黑了，来个算法题为你助眠

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。

返回 你能获得的最大积分和 。

示例 1：

输入：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 分)

示例2：

输入：boxes = [1,1,1]

输出：9

示例3： 

 输入：boxes = [1]

输出：1

提示：

• 1 <= boxes.length <= 100
• 1 <= boxes[i] <= 100

// 无缓存数组版本
public int removeBoxes(int[] boxes) {
    if (boxes == null || boxes.length < 1) return 0;
    if (boxes.length == 1) return 1;
    return process(boxes, 0, boxes.length - 1, 0);
}
 
// 在前面有 k 个数与 arr[L] 相同的情况下
// 移除 L ~ R 的盒子，得到的最大得分
public int process(int[] arr, int L, int R, int k) {
    if (L > R) return 0;
    // 如果arr[L]的数与前面的一起消掉
    int ans = process(arr, L + 1, R, 0) + (k + 1) * (k + 1);
    // arr[L] 和前面的 k 个数一起作为下一个等于arr[L] 没有消掉的数
    for (int i = L + 1; i <= R; i++) {
        if (arr[i] == arr[L]) {
            ans = Math.max(ans, process(arr, L + 1, i - 1, 0) + process(arr,i, R, k + 1));
        }
    }
    return ans;
}
 
 
// 通过缓存数组大幅提升速度
// 与前面的方法是一样的道理，只不过用了一个数组存了算过的东西避免递归时反复计算浪费时间
public static int removeBoxes(int[] boxes) {
    int N = boxes.length;
    int[][][] dp = new int[N][N][N];
    return process(boxes, 0, boxes.length - 1, 0, dp);
}
 
public static int process(int[] arr, int L, int R, int K, int[][][] dp) {
    if (L > R) return 0;
    if (dp[L][R][K] != 0) return dp[L][R][K];
    int max = process(arr, L + 1, R, 0, dp) + (K + 1) * (K + 1);
    for (int i = L + 1; i <= R; i++) {
        if (arr[i] == arr[L]) {
            max = Math.max(max,
                    process(arr, L + 1, i - 1, 0, dp) + process(arr, i, R, K + 1, dp));
        }
    }
    dp[L][R][K] = max;
    return max;
}
 
// 进一步优化常数项时间
public static int removeBoxes(int[] boxes) {
    int N = boxes.length;
    int[][][] dp = new int[N][N][N];
    return process(boxes, 0, boxes.length - 1, 0, dp);
}
 
// 如果arr[L]后面有和它相等的一串数，假设到 last 都是和 arr[L] 相等的，
// 那么直接把 原来前面K个和 L ~ last - 1 位置的数当成last位置前面与其相等的部分 
public static int process(int[] arr, int L, int R, int K, int[][][] dp) {
    if (L > R) return 0;
    if (dp[L][R][K] != 0) return dp[L][R][K];
    int last = L;
    while (last + 1 <= R && arr[last + 1] == arr[L]) {
        last++;
    }
    int pre = last - L + K;
    int max = process(arr, last + 1, R, 0, dp) + (pre + 1) * (pre + 1);
    for (int i = last + 2; i <= R; i++) {
        if (arr[i] == arr[L] && arr[i - 1] != arr[L]) {
            max = Math.max(max,
                           process(arr, last + 1, i - 1, 0, dp) + process(arr, i, R, pre + 1, dp));
        }
    }
    dp[L][R][K] = max;
    return max;
}

题目来源：546. 移除盒子

打败 100% 。虽然看了大佬题解，但看懂后写出来也很高兴