西安网站建设有限公司,建设网站的优势,连云港建设局官方网站,怎样做txt电子书下载网站文章目录1. 题目2. 解题1. 题目
给出一些不同颜色的盒子#xff0c;盒子的颜色由数字表示#xff0c;即不同的数字表示不同的颜色。 你将经过若干轮操作去去掉盒子#xff0c;直到所有的盒子都去掉为止。
每一轮你可以移除具有相同颜色的连续 k 个盒子#xff08;k …
文章目录1. 题目2. 解题1. 题目
给出一些不同颜色的盒子盒子的颜色由数字表示即不同的数字表示不同的颜色。 你将经过若干轮操作去去掉盒子直到所有的盒子都去掉为止。
每一轮你可以移除具有相同颜色的连续 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*39 分)
---- [1, 3, 3, 3, 1] (1*11 分)
---- [1, 1] (3*39 分)
---- [] (2*24 分)提示
1 boxes.length 100
1 boxes[i] 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/remove-boxes 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考官方的思路dp[i][j][k] 表示区间[i,j]后面有 k 个连续元素跟 j 下标处相同两种办法1消除右侧的k1个一样的 dp[i][j][k] dp[i][j-1][0] (k1)*(k1)2枚举左侧的中间点 p in [i, j-1]当b[p]b[j]时消除[p1,j-1]区间dp[i][j][k] dp[p1][j-1][0] dp[i][p][k1]
class Solution {//显示全过了但是超时
public:int removeBoxes(vectorint boxes) {int dp[101][101][101];memset(dp, 0, sizeof dp);//dp[i][j][k] 表示区间[i,j]后面有 k 个连续元素跟 j 相同 int n boxes.size(), i, j, k, p, len;for(len 1; len n; len) {for(i 0; ilen-1 n; i){j ilen-1;for(k 0; k n; k){//策略1//消除右侧的k1个一样的dp[i][j][k] max(dp[i][j][k], (j-1 i ? 0 : dp[i][j-1][0])(k1)*(k1));for(p i; p j-1; p){//策略2, 消除[p1,j-1]区间b[p]b[j]时if(boxes[p] boxes[j]){dp[i][j][k] max(dp[i][j][k], (p1 j-1 ? 0 : dp[p1][j-1][0]) dp[i][p][k1]);}}}}}return dp[0][n-1][0];}
};class Solution { //官方解答代码
public:int dp[100][100][100];int removeBoxes(vectorint boxes) {memset(dp, 0, sizeof dp);return calculatePoints(boxes, 0, boxes.size() - 1, 0);}int calculatePoints(vectorint boxes, 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 boxes[r] boxes[r - 1]) {r--;k;}dp[l][r][k] calculatePoints(boxes, l, r - 1, 0) (k 1) * (k 1);for (int i l; i r; i) {if (boxes[i] boxes[r]) {dp[l][r][k] max(dp[l][r][k], calculatePoints(boxes, l, i, k 1) calculatePoints(boxes, i 1, r - 1, 0));}}return dp[l][r][k];}
};我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
