原題目鏈接：移除盒子

1. 題目?jī)?nèi)容：
   給出一些不同顏色的盒子，盒子的顏色由數(shù)字表示，即不同的數(shù)字表示不同的顏色。你將經(jīng)過(guò)若干輪操作去去掉盒子，直到所有的盒子都去掉為止。每一輪你可以移除具有相同顏色的連續(xù) k 個(gè)盒子（k >= 1），這樣一輪之后你將得到 k*k 個(gè)積分。當(dāng)你將所有盒子都去掉之后，求你能獲得的最大積分和。
2. 為什么要進(jìn)行優(yōu)化？
   因?yàn)槲铱吹筋}目想到了將盒子按顏色進(jìn)行分塊的想法，結(jié)合官方題解便有了此代碼。而且官方的題解在跑一個(gè)我自己的測(cè)試用例的時(shí)候超時(shí)，而優(yōu)化后的代碼依舊保持良好的性能。
   該測(cè)試用例如下：

[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]

分別用兩個(gè)代碼測(cè)試該用例。

官方題解測(cè)試

優(yōu)化后代碼用時(shí)

3. 思想是將相鄰的同顏色盒子看成一個(gè)整體，因?yàn)橐粋€(gè)最優(yōu)解不可能會(huì)將相鄰?fù)伾凶臃珠_(kāi)移除而取得。那么可有效地減少這類(lèi)測(cè)試用例中的計(jì)算量。
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;
    }
}