Remove Boxes Hard 0 attempts
LeetCode ↗

Remove Boxes

Hard GraphBFSDFS LeetCode

You have a row of colored boxes given as boxes. In each move, pick a maximal run of consecutive boxes that share the same color and remove the entire run at once, earning k^2 points where k is the number of boxes removed in that move. Keep making moves until no boxes remain, and find the highest total score you can achieve.

Input Format
Implement removeBoxes(boxes). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
boxes = [1,3,2,2,2,3,4,3,1]
Output
23

Example 2

Input
boxes = [1,1,1]
Output
9
Constraints
  • 1 <= boxes.length <= 100
  • 1 <= boxes[i] <= 100
Test Cases (2)
Case 1
Args: [[1,3,2,2,2,3,4,3,1]] Expected: 23
Case 2
Args: [[1,1,1]] Expected: 9
Topics
GraphBFSDFS

3D Interval DP

dp[l][r][k] = max points from boxes[l..r] with k extra boxes same as boxes[r] appended.

javascript
function removeBoxes(boxes) {
  const n = boxes.length;
  const dp = Array.from({length:n}, ()=>Array.from({length:n}, ()=>Array(n).fill(0)));
  function solve(l, r, k) {
    if (l > r) return 0;
    if (dp[l][r][k]) return dp[l][r][k];
    let res = solve(l, r-1, 0) + (k+1)*(k+1);
    for (let i = l; i < r; i++)
      if (boxes[i] === boxes[r])
        res = Math.max(res, solve(l, i, k+1) + solve(i+1, r-1, 0));
    return dp[l][r][k] = res;
  }
  return solve(0, n-1, 0);
}

Time: O(n⁴) | Space: O(n³)

Saved in this browser only. Private to you.

JavaScript