classSolution{public:intremoveBoxes(vector<int>&boxes){constintn=boxes.size();vector<vector<vector<int>>>mem(n,vector<vector<int>>(n,vector<int>(n)));returnremoveBoxes(boxes,0,n-1,0,mem);}private:// Returns the maximum score of boxes[i..j] if k boxes eqaul to boxes[j].intremoveBoxes(constvector<int>&boxes,inti,intj,intk,vector<vector<vector<int>>>&mem){if(i>j)return0;if(mem[i][j][k]>0)returnmem[i][j][k];intr=j;intsameBoxes=k+1;while(r>0&&boxes[r-1]==boxes[r]){--r;++sameBoxes;}mem[i][j][k]=removeBoxes(boxes,i,r-1,0,mem)+sameBoxes*sameBoxes;for(intp=i;p<r;++p)if(boxes[p]==boxes[r])mem[i][j][k]=max(mem[i][j][k],removeBoxes(boxes,i,p,sameBoxes,mem)+removeBoxes(boxes,p+1,r-1,0,mem));returnmem[i][j][k];}};
classSolution{publicintremoveBoxes(int[]boxes){finalintn=boxes.length;int[][][]mem=newint[n][n][n];returnremoveBoxes(boxes,0,n-1,0,mem);}// Returns the maximum score of boxes[i..j] if k boxes are equal to boxes[j]privateintremoveBoxes(int[]boxes,inti,intj,intk,int[][][]mem){if(i>j)return0;if(mem[i][j][k]>0)returnmem[i][j][k];intr=j;intsameBoxes=k+1;while(r>0&&boxes[r-1]==boxes[r]){--r;++sameBoxes;}mem[i][j][k]=removeBoxes(boxes,i,r-1,0,mem)+sameBoxes*sameBoxes;for(intp=i;p<r;++p)if(boxes[p]==boxes[r])mem[i][j][k]=Math.max(mem[i][j][k],removeBoxes(boxes,i,p,sameBoxes,mem)+removeBoxes(boxes,p+1,r-1,0,mem));returnmem[i][j][k];}}
1 2 3 4 5 6 7 8 9101112131415161718192021222324
classSolution:defremoveBoxes(self,boxes:list[int])->int:@functools.lru_cache(None)defdp(i:int,j:int,k:int)->int:""" Returns the maximum score of boxes[i..j] if k boxes equal to boxes[j]. """ifi>j:return0r=jsameBoxes=k+1whiler>0andboxes[r-1]==boxes[r]:r-=1sameBoxes+=1res=dp(i,r-1,0)+sameBoxes*sameBoxesforpinrange(i,r):ifboxes[p]==boxes[r]:res=max(res,dp(i,p,sameBoxes)+dp(p+1,r-1,0))returnresreturndp(0,len(boxes)-1,0)
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! π