要解此题,要明白两种策略:
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];
}
}
网友评论