546. 移除盒子

旧城等待， 2022-11-27 12:22 222阅读 0赞

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。  
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。  
当你将所有盒子都去掉之后，求你能获得的最大积分和。  
输入：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 分)  
\*\*思路：\*\*动态规划

dp[101][101][101];
    int fun(int *b,int l,int r,int k)
    { 
        if(l>r)return 0;
        if(dp[l][r][k]!=0)return dp[l][r][k];
        while(r>l&&b[r]==b[r-1])
        { 
            r--;
            k++;
        }
        
        //把b[r]后面相同的k个数删除
        dp[l][r][k]=fun(b,l,r-1,0)+(k+1)*(k+1);
    
        for(int i=l;i<r;i++)
        { 
            if(b[i]==b[r])
            { 
                int temp=fun(b,l,i,k+1)+fun(b,i+1,r-1,0);
                if(dp[l][r][k]<temp)
                { 
                    dp[l][r][k]=temp;
                }
            }
        }
        return dp[l][r][k];
    }
    int removeBoxes(int* boxes, int boxesSize){ 
        memset(dp,0,sizeof(dp));
        return fun(boxes,0,boxesSize-1,0);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，222人围观）

还没有评论，来说两句吧...

相关阅读

相关移除元素

给你一个数组 nums 和一个值 val，你需要 [原地][Link 1] 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用

「爱情、让人受尽委屈。」/ 2023年07月23日 08:56/ 0 赞/ 14 阅读

相关 [Leetcode][第546题][JAVA][移除盒子][递归][动态规划]

【问题描述】\[困难\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

你的名字/ 2022年11月27日 15:36/ 0 赞/ 160 阅读

相关 546. 移除盒子

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k

旧城等待，/ 2022年11月27日 12:22/ 0 赞/ 223 阅读

相关 27.移除元素

题目描述：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1)

灰太狼/ 2022年09月11日 05:25/ 0 赞/ 250 阅读

相关 python 元素移除

给定一个数组和一个数（该数不一定在数组中），从数组里删掉这个数字，返回剩下的数组长度。如：A\[\]=1,2,3,4,5A\[\] = \{1, 2, 3, 4,

秒速五厘米/ 2022年06月08日 07:10/ 0 赞/ 337 阅读

相关 LeetCode——移除元素

题目：给定一个数组 nums 和一个值 val，你需要[原地][Link 1]移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在

Love The Way You Lie/ 2022年05月19日 11:35/ 0 赞/ 303 阅读

相关 checkBox 选中移除

> checkBox 选中移除（1）使用原生JavaScript判断是否选中checkbox框（js） <input type="checkbox"

忘是亡心i/ 2022年05月09日 14:42/ 0 赞/ 284 阅读

相关移除元素

题目描述给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数

冷不防/ 2021年12月14日 03:35/ 0 赞/ 368 阅读

相关 Iterator移除元素

iterator移除元素 > 移除list的某些元素 demo / 搜索 / public String search(WhiteScreenS

本是古典何须时尚/ 2021年12月11日 21:15/ 0 赞/ 415 阅读

相关 LeetCode移除元素

题目描述给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组

水深无声/ 2021年11月05日 07:34/ 0 赞/ 575 阅读