对于Leetcode题目移除盒子官方题解的优化

原题目链接：移除盒子

1. 题目内容：
   给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。当你将所有盒子都去掉之后，求你能获得的最大积分和。
2. 为什么要进行优化？
   因为我看到题目想到了将盒子按颜色进行分块的想法，结合官方题解便有了此代码。而且官方的题解在跑一个我自己的测试用例的时候超时，而优化后的代码依旧保持良好的性能。
   该测试用例如下：

[1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,1,4,1,1,1,1,1,1,1,1,1,5,1,1,1,1,1,1,1,1,1,6,1,1,1,1,1,1,1,1,1,5,1,1,1,1,1,1,1,1,1,4,1,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1]

分别用两个代码测试该用例。

官方题解测试

优化后代码用时

3. 思想是将相邻的同颜色盒子看成一个整体，因为一个最优解不可能会将相邻同颜色盒子分开移除而取得。那么可有效地减少这类测试用例中的计算量。
4. 具体代码如下：

class Solution {
    int[][][] dp;
    int[] colorArray;
    int[] countArray;
    public int removeBoxes(int[] boxes) {
        List<Integer> colorList = new ArrayList<Integer>();
        List<Integer> countList = new ArrayList<Integer>();
        int color = boxes[0];
        int count = 0;
        for(int i = 0;i < boxes.length;++i){
            if(boxes[i] == color){
                count++;
            }
            else{
                colorList.add(color);
                countList.add(count);
                color = boxes[i];
                count = 1;
            }
        }
        colorList.add(color);
        countList.add(count);
        int size = colorList.size();
        colorArray = new int[size];
        for(int i = 0;i < size;++i){
            colorArray[i] = colorList.get(i);
        }
        countArray = new int[size];
        for(int i = 0;i < size;++i){
            countArray[i] = countList.get(i);
        }
        dp = new int[size][size][100];
        return calculatePoints(0,size - 1,0);
    }
    public int calculatePoints(int l,int r,int count){
        if(l > r){
            return 0;
        }
        if(dp[l][r][count] != 0){
            return dp[l][r][count];
        }
        int max = calculatePoints(l,r-1,0) + (countArray[r] + count)*(countArray[r] + count);
        for(int i = l;i < r;++i){
            if(colorArray[i] == colorArray[r]){
                max = Math.max(max,calculatePoints(l,i,count + countArray[r]) + calculatePoints(i+1,r-1,0));
            }
        }
        dp[l][r][count] = max;
        return max;
    }
}