546. 移除盒子

image.png

要解此题，要明白两种策略：
1：后面这四个是一个颜色，我会直接将他们消除，不去考虑前面的部分

image.png

2：第二种策略还会去考虑前面的部分，还有没有可以消除的部分。相当于去遍历前面的所有节点，如果还有相似部分，就先将中间的间隔部分消除，然后再一起消除

image.png
image.png
image.png
我们要去比较这两种方法到底哪一个，得到的积分是最大的

class Solution {
    int [][][] dp=new int[100][100][100];
    public int removeBoxes(int[] boxes) {
       return dfs(0,boxes.length-1,0,boxes);
    }

    private int dfs(int left, int right, int count,int [] boxes) {
       if(left>right) return 0;
       if(dp[left][right][count]!=0) return dp[left][right][count];
       while(right>left&&boxes[right]==boxes[right-1]){
           right--;
           count++;
       }
       dp[left][right][count]=dfs(left,right-1,0,boxes)+(count+1)*(count+1);
       for(int i=left;i<=right-1;i++){
           if(boxes[i]==boxes[right]){
              dp[left][right][count]=Math.max(dp[left][right][count],dfs(left,i,count+1,boxes)+dfs(i+1,right-1,0,boxes));
           }
       }
       return dp[left][right][count];
    }
}