## Algorithm

Problem Name: 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`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const removeBoxes = function(boxes) {
const n = boxes.length
const dp = Array.from(new Array(n), () => {
return Array.from(new Array(n), () => {
return new Array(n).fill(0)
})
})
return removeBoxesSub(boxes, 0, n - 1, 0, dp)
};

function removeBoxesSub(boxes, i, j, k, dp) {
if(i > j) return 0;
if(dp[i][j][k] > 0) return dp[i][j][k]
for(; i + 1 <= j && boxes[i+1] === boxes[i] ; i++, k++) {
// optimization: all boxes of the same color counted continuously from the first box should be grouped together
}
let res = (k+1) * (k+1) + removeBoxesSub(boxes, i + 1, j, 0, dp)
for(let m = i + 1; m  < = j; m++) {
if(boxes[i] === boxes[m]) {
res = Math.max(res, removeBoxesSub(boxes, i + 1, m - 1, 0, dp) + removeBoxesSub(boxes, m, j, k + 1, dp) >
}
}
dp[i][j][k] = res
return res
}
``````
Copy The Code &

Input

cmd
boxes = [1,3,2,2,2,3,4,3,1]

Output

cmd
23

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def removeBoxes(self, A):
n = len(A)
memo = [[[0] * n for _ in range(n) ] for _ in range(n)]
def dp(i, j, k):
if i > j: return 0
if not memo[i][j][k]:
m = i
while m+1 <= j and A[m+1] == A[i]:
m += 1
i, k = m, k + m - i
ans = dp(i+1, j, 0) + (k+1) ** 2
for m in range(i+1, j+1):
if A[i] == A[m]:
ans = max(ans, dp(i+1, m-1, 0) + dp(m, j, k+1))
memo[i][j][k] = ans
return memo[i][j][k]
return dp(0, n-1, 0)
``````
Copy The Code &

Input

cmd
boxes = [1,3,2,2,2,3,4,3,1]

Output

cmd
23