​LeetCode刷题实战546：移除盒子

示例 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

class Solution {
public:
    //题意中最大100
    int dp[101][101][101];
    
    int dfs(vector<int>&boxes,int l,int r,int k){
      //终止条件
        if(l>r)
            return 0;
        //先找出当前的最右边的连续相同的箱子
        while(r>l&&boxes[r]==boxes[r-1]){
            --r;
            ++k;
        }
        //若之前计算过，直接返回
        if(dp[l][r][k]>0)
            return dp[l][r][k];
        //先计算（2）中的情况，既直接将最右边的相同的箱子消去
        dp[l][r][k]=dfs(boxes,l,r-1,0)+(k+1)*(k+1);
        
        //计算（3）中的情况，既在左边的数组中找出可以和右侧连续的箱子结合的情形
        for(int i=l;i            if(boxes[i]==boxes[r]){
                dp[l][r][k]=max(dp[l][r][k],dfs(boxes,l,i,k+1)+dfs(boxes,i+1,r-1,0));
            }
        }
        //返回当前情形
        return dp[l][r][k];
    }
    
    int removeBoxes(vector<int>& boxes) {
        return dfs(boxes,0,boxes.size()-1,0);
    }
};