美文网首页
546. 移除盒子

546. 移除盒子

作者: bangbang2 | 来源:发表于2020-08-16 10:25 被阅读0次
image.png

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

相关文章

  • 546. 移除盒子

    要解此题,要明白两种策略:1:后面这四个是一个颜色,我会直接将他们消除,不去考虑前面的部分 2:第二种策略还会去考...

  • 546. 移除盒子【DP】

    分析:暴力法 以1121134为例,肯定要尽量地将不连续的块连续起来,一并删除。这样收益较大。因为(1+1)^2 ...

  • Leetcode每日一题(1)

    546. 移除盒子 给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。你将经过若干轮操作去...

  • 8.24 - hard - 101

    546. Remove Boxes 先做出来一个backtracking的TLE版本,下面想想如何加memory,...

  • 546.交流

    早上,背诗群有一个河北的群友发了一个“小年”红包,因为好多群友过得小年都是腊月二十三,没有过过“六月初一”的,群友...

  • 546. Remove Boxes

    ?http://www.cnblogs.com/grandyang/p/6850657.html Solution...

  • 546.冷与静

    一人灭一国和一人灭十国哪个厉害,乍看之下可能是灭十国厉害,但不是这么简单就能比较的,比如说一国是大国,万众一心坚如...

  • 546. 冻融风化

  • Java集合遇到的坑

    1. 集合List在移除元素时会报数组越界异常或者移除不该移除的元素 原因: 集合的移除元素可以...

  • 1.6 上线实操之移除订单

    创建移除订单 从【管理库存】页面或【建议移除】报告中创建移除订单。您可以通过【管理库存】页面选择您要移除的任何库存...

网友评论

      本文标题:546. 移除盒子

      本文链接:https://www.haomeiwen.com/subject/sqdadktx.html