# Remove Boxes LeetCode Solution

Here, We see Remove Boxes LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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

## Remove Boxes LeetCode Solution C++

``````class Solution {
public:
int dp[102][102][102];
int solve(int i, int j, int extra, vector<pair<int, int>> &groups)
{
if (i > j)
return 0;
if (dp[i][j][extra] != -1)
return dp[i][j][extra];
int ans = (groups[i].second + extra) * (groups[i].second + extra) + solve(i + 1, j, 0, groups);
for (int g = i + 1; g <= j; g++)
if (groups[g].first == groups[i].first)
ans = max(ans, solve(i + 1, g - 1, 0, groups) + solve(g, j, extra + groups[i].second, groups));
return dp[i][j][extra] = ans;
}
int removeBoxes(vector<int> &boxes)
{
int n = boxes.size();
vector<pair<int, int>> groups;
for (int i = 0; i < n; i++)
{
int j = i;
while (i + 1 < n and boxes[i + 1] == boxes[j])
i++;
groups.push_back({boxes[j], i - j + 1});
}
memset(dp, -1, sizeof(dp));
return solve(0, groups.size() - 1, 0, groups);
}
};```Code language: PHP (php)```

## Remove Boxes LeetCode Solution Java

``````class Solution {
public int removeBoxes(int[] boxes) {
int n = boxes.length;
int[][][] memo = new int[n][n][n];
return removeBoxesSub(boxes, 0, n - 1, 0, memo);
}
private int removeBoxesSub(int[] boxes, int i, int j, int k, int[][][] memo) {
if (i > j) return 0;
if (memo[i][j][k] > 0) return memo[i][j][k];
int tmpi = i, tmpk = k;
while (i + 1 <= j && boxes[i + 1] == boxes[i]) {
i++;
k++;
}
int res = (k + 1) * (k + 1) + removeBoxesSub(boxes, i + 1, j, 0, memo);
for (int m = i + 1; m <= j; m++) {
if (boxes[i] == boxes[m]) {
res = Math.max(res, removeBoxesSub(boxes, i + 1, m - 1, 0, memo) + removeBoxesSub(boxes, m, j, k + 1, memo));
}
}
memo[tmpi][j][tmpk] = res;
return res;
}
}```Code language: PHP (php)```

## Remove Boxes Solution JavaScript

``````var removeBoxes = function (boxes) {
const merged = []
const points = []
let count = 1

for (let i = 0; i < boxes.length; i++) {
if (boxes[i] !== boxes[i + 1]) {
merged.push(boxes[i])
points.push(count)
count = 1
continue
}
count++
}

const size = merged.length;
const dp = Array.from({ length: size }, () => Array.from({ length: size }, () => new Uint16Array(boxes.length)))
const calculate = (l, r, p) => {
if (l > r) {
return 0
}
if (dp[l][r][p]) {
return dp[l][r][p]
}
let point = points[l] + p
let max = point * point + calculate(l + 1, r, 0)
for (let i = l + 1; i <= r; i++) {
if (merged[i] === merged[l]) {
max = Math.max(max, calculate(l + 1, i - 1, 0) + calculate(i, r, point))
}
}
dp[l][r][p] = max
return max
}
return calculate(0, size - 1, 0)
}```Code language: JavaScript (javascript)```

## Remove Boxes Solution Python

``````class Solution(object):
def removeBoxes(self, boxes):
def dp(i, j, k):
if i > j:
return 0
while i < j and boxes[j] == boxes[j-1]:
j -= 1
k += 1
if i == j:
return (k+1)**2
ans = (k+1)**2 + dp(i, j-1, 0)
for m in range(j-1, i-1, -1):
if boxes[m] == boxes[j]:
ans = max(ans, dp(i, m, k+1) + dp(m+1, j-1, 0))
return ans
return dp(0, len(boxes)-1, 0)```Code language: HTML, XML (xml)```
Scroll to Top