?LeetCode刷題實(shí)戰(zhàn)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;
????????//先找出當(dāng)前的最右邊的連續(xù)相同的箱子
????????while(r>l&&boxes[r]==boxes[r-1]){
????????????--r;
????????????++k;
????????}
????????//若之前計(jì)算過，直接返回
????????if(dp[l][r][k]>0)
????????????return?dp[l][r][k];
????????//先計(jì)算（2）中的情況，既直接將最右邊的相同的箱子消去
????????dp[l][r][k]=dfs(boxes,l,r-1,0)+(k+1)*(k+1);
????????
????????//計(jì)算（3）中的情況，既在左邊的數(shù)組中找出可以和右側(cè)連續(xù)的箱子結(jié)合的情形
????????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));
????????????}
????????}
????????//返回當(dāng)前情形
????????return?dp[l][r][k];
????}
????
????int?removeBoxes(vector<int>& boxes)?{
????????return?dfs(boxes,0,boxes.size()-1,0);
????}
};