You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get k*k points.Find the maximum points you can get.
给定若干个不同颜色的盒子，用不同数字表示。每次选择连续的k个相同颜色的箱子进行消除，消除一次得到k*k的分数，直到把所有箱子消除，求最多能得到的分数。
思路：这道题和之前做过的Burst Balloons很相似http://blog.csdn.net/lizhb5/article/details/68490522，都是将一个区间的长度由n缩小为1，而且缩小的规则都与左右两边的数字有关系。所以用枚举的方法显然是不行的，由以前的题启发可知，显然这道题要用动态规划来做。仿照上一题的做法，建立一个二维数组dp[left][right]记录区间[left,right]之间的最大得分。但是这道题消除的规则有些不一样，是对连续k个相同颜色的箱子进行消除，所以状态转移的时候需要增加一维记录这个k，要建立一个三维数组dp[left][right][k]表示，区间[left,right]之间，并且right之后还有k个颜色与right相同的箱子能得到的最大分数。那么dp[left][right][k] = dp[left][right-1][0] + (len[right]+k)*(len[right]+k)。在区间left和right之间任意一个点如果能进行消除，那么就要更新分数，假设 消除的点为i，那么dp[left][right][k] = max(dp[left][right][k], dp[left][i][len(r)+k]+dp[i+1][right][0])。直到区间的left比right大，就结束更新，得到最大的分数了。
class Solution { public: int removeBoxes(vector<int>& boxes) { int n=boxes.size(); int dp[100][100][100] = {0};//三维数组记录得分 return dfs(boxes,dp,0,n-1,0); } int dfs(vector<int>& boxes, int dp[100][100][100],int left, int right, int length) { if(left > right)//假如左边的坐标大于右边，得0分 return 0; if(dp[left][right][length] != 0) return dp[left][right][length]; while(right > 1 && boxes[right] == boxes[right-1])//统计连续几个相同的盒子 { length++; right--; } dp[left][right][length] = dfs(boxes,dp,left,right-1,0) + (length+1)*(length+1);//计算合并后的得分 for(int i = left; i < right; ++i) { if(boxes[i] == boxes[right]) dp[left][right][length] = max(dp[left][right][length], dfs(boxes,dp, left,i,length+1)//中间合并后更新分数 +dfs(boxes,dp,i+1,right-1,0)); } return dp[left][right][length]; } };