# 546. Remove Boxes

You are given several `boxes` with different colors represented by different positive numbers.

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 (i.e., composed of `k` boxes, `k >= 1`), remove them and get `k * k` points.

Return  the maximum points you can get.

Example 1:

``````Input: boxes = [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
----> [1, 3, 3, 3, 1] (1*1=1 points)
----> [1, 1] (3*3=9 points)
----> [] (2*2=4 points)
``````

Example 2:

``````Input: boxes = [1,1,1]
Output: 9
``````

Example 3:

``````Input: boxes = [1]
Output: 1
``````

Constraints:

• `1 <= boxes.length <= 100`
• `1 <= boxes[i] <= 100`

``````class Solution {
public:
int removeBoxes(vector<int>& boxes) {
int n = boxes.size();
int dp[100][100][100] = {0};
return helper(boxes, 0, n - 1, 0, dp);
}
int helper(vector<int>& boxes, int i, int j, int k, int dp[100][100][100]) {
if (j < i) return 0;
if (dp[i][j][k] > 0) return dp[i][j][k];
int res = (1 + k) * (1 + k) + helper(boxes, i + 1, j, 0, dp);
for (int m = i + 1; m <= j; ++m) {
if (boxes[m] == boxes[i]) {
res = max(res, helper(boxes, i + 1, m - 1, 0, dp) + helper(boxes, m, j, k + 1, dp));
}
}
return dp[i][j][k] = res;
}
};
``````

``````class Solution {
public:
int removeBoxes(vector<int>& boxes) {
int n = boxes.size();
int dp[n][n][n] = {0};
for (int i = 0; i < n; ++i) {
for (int k = 0; k <= i; ++k) {
dp[i][i][k] = (1 + k) * (1 + k);
}
}
for (int t = 1; t < n; ++t) {
for (int j = t; j < n; ++j) {
int i = j - t;
for (int k = 0; k <= i; ++k) {
int res = (1 + k) * (1 + k) + dp[i + 1][j][0];
for (int m = i + 1; m <= j; ++m) {
if (boxes[m] == boxes[i]) {
res = max(res, dp[i + 1][m - 1][0] + dp[m][j][k + 1]);
}
}
dp[i][j][k] = res;
}
}
}
return n == 0 ? 0 : dp[0][n - 1][0];
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/546

Burst Balloons

Zuma Game

Strange Printer

https://leetcode.com/problems/remove-boxes/

https://leetcode.com/problems/remove-boxes/discuss/101312/memoization-dfs-c

https://leetcode.com/problems/remove-boxes/discuss/101310/java-top-down-and-bottom-up-dp-solutions

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation