Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2

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

Example 3

1
2

Input: boxes = [1]
Output: 1

Method 1 - Naive Recursion

Intuition

This approach tries every possible way to remove boxes, always choosing the best option at each step. At each recursive call, we can remove a contiguous group of boxes of the same color, or skip and try other possibilities. The recursion explores all possible removal orders, which leads to a recursion tree.

Approach

For each contiguous group of boxes of the same color, we can:

  1. Remove the group and get k*k points, then recursively solve the remaining boxes.
  2. Skip the group and try other possible removals, recursively. We take the maximum score among all possible choices.

Recurrence Relation

Let f(boxes) be the maximum score for a given configuration:

  • For each contiguous group of length k at the start, f(boxes) = max(f(remaining) + k*k) for all possible groups.

Base Case

If there are no boxes left, return 0. If only one box remains, return 1.

See the diagram below for more understanding:

---
title: boxes=[1,2,1]
---

graph TD
    A([1,2,1])
    A -.->|"max(3,5,3) = 5"| Z("Ans")
    A -->|remove 1| B([2,1]):::remove1
    A -->|remove 2| C([1,1]):::remove2
    A -->|remove 1| D([1,2]):::remove1
    
    B -->|remove 2| E([1]):::remove2
    B -->|remove 1| F([2]):::remove1
    
    D -->|remove 1| G([2]):::remove1
    D -->|remove 2| H([1]):::remove2
    
    E -->|remove 1| N1("null"):::remove1
    N1 -.->|⏎ 1| E
    E -.->|⏎ 1+1| B
    B -.->|"⏎ max(2,2) + 1 = 3"| A
    
    F -->|remove 2| N2("null"):::remove2
    N2 -.->|⏎ 1| F
    F -.->|⏎ 1+1| B
    
    C -->|remove 1| N3("null"):::remove1
    N3 -.->|⏎ 4| C
    C -.->|⏎ 4 + 1| A
    
    G -->|remove 2| N4("null"):::remove2
    N4 -.->|⏎ 1| G
    G -.->|⏎ 1+1| D
    D -.->|"⏎ max(2,2) + 1 = 3"| A
    
    H -->|remove 1| N5("null"):::remove1
    N5 -.->|⏎ 1| H
    H -.->|⏎ 1+1| D    

    classDef remove1 fill:#f9f,stroke:#333,stroke-width:2px;
    classDef remove2 fill:#bbf,stroke:#333,stroke-width:2px;
    classDef green fill:#44ff44,stroke:#333,stroke-width:2px;

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        return dfs(boxes);
    }
    int dfs(vector<int> boxes) {
        if (boxes.empty()) return 0;
        int maxScore = 0;
        int n = boxes.size();
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && boxes[j] == boxes[i]) ++j;
            int k = j - i;
            vector<int> next;
            next.insert(next.end(), boxes.begin(), boxes.begin() + i);
            next.insert(next.end(), boxes.begin() + j, boxes.end());
            maxScore = max(maxScore, dfs(next) + k * k);
            i = j;
        }
        return maxScore;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func removeBoxes(boxes []int) int {
    var dfs func([]int) int
    dfs = func(boxes []int) int {
        if len(boxes) == 0 {
            return 0
        }
        maxScore := 0
        n := len(boxes)
        i := 0
        for i < n {
            j := i
            for j < n && boxes[j] == boxes[i] {
                j++
            }
            k := j - i
            next := append([]int{}, boxes[:i]...)
            next = append(next, boxes[j:]...)
            score := dfs(next) + k*k
            if score > maxScore {
                maxScore = score
            }
            i = j
        }
        return maxScore
    }
    return dfs(boxes)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int removeBoxes(int[] boxes) {
        return dfs(boxes);
    }
    private int dfs(int[] boxes) {
        if (boxes.length == 0) return 0;
        int maxScore = 0, n = boxes.length;
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && boxes[j] == boxes[i]) ++j;
            int k = j - i;
            int[] next = new int[i + n - j];
            System.arraycopy(boxes, 0, next, 0, i);
            System.arraycopy(boxes, j, next, i, n - j);
            maxScore = Math.max(maxScore, dfs(next) + k * k);
            i = j;
        }
        return maxScore;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun removeBoxes(boxes: IntArray): Int {
        fun dfs(boxes: IntArray): Int {
            if (boxes.isEmpty()) return 0
            var maxScore = 0
            var i = 0
            val n = boxes.size
            while (i < n) {
                var j = i
                while (j < n && boxes[j] == boxes[i]) j++
                val k = j - i
                val next = boxes.sliceArray(0 until i) + boxes.sliceArray(j until n)
                maxScore = maxOf(maxScore, dfs(next) + k * k)
                i = j
            }
            return maxScore
        }
        return dfs(boxes)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        def dfs(boxes):
            if not boxes:
                return 0
            maxScore = 0
            n = len(boxes)
            i = 0
            while i < n:
                j = i
                while j < n and boxes[j] == boxes[i]:
                    j += 1
                k = j - i
                next_boxes = boxes[:i] + boxes[j:]
                maxScore = max(maxScore, dfs(next_boxes) + k * k)
                i = j
            return maxScore
        return dfs(boxes)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn remove_boxes(boxes: Vec<i32>) -> i32 {
        fn dfs(boxes: &[i32]) -> i32 {
            if boxes.is_empty() {
                return 0;
            }
            let mut max_score = 0;
            let n = boxes.len();
            let mut i = 0;
            while i < n {
                let mut j = i;
                while j < n && boxes[j] == boxes[i] {
                    j += 1;
                }
                let k = j - i;
                let mut next = Vec::with_capacity(i + n - j);
                next.extend_from_slice(&boxes[..i]);
                next.extend_from_slice(&boxes[j..]);
                max_score = max_score.max(dfs(&next) + (k * k) as i32);
                i = j;
            }
            max_score
        }
        dfs(&boxes)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    removeBoxes(boxes: number[]): number {
        function dfs(boxes: number[]): number {
            if (boxes.length === 0) return 0;
            let maxScore = 0;
            let i = 0;
            const n = boxes.length;
            while (i < n) {
                let j = i;
                while (j < n && boxes[j] === boxes[i]) j++;
                const k = j - i;
                const next = boxes.slice(0, i).concat(boxes.slice(j));
                maxScore = Math.max(maxScore, dfs(next) + k * k);
                i = j;
            }
            return maxScore;
        }
        return dfs(boxes);
    }
}

Complexity

  • ⏰ Time complexity: O(2^n), since every subset of boxes can be considered in the worst case.
  • 🧺 Space complexity: O(n), due to recursion stack.

Method 2 - Top Down Dynamic Programming (Memoization)

Intuition

The naive recursion repeats many subproblems. By using memoization, we can cache results for each subarray and avoid redundant computation. The key is to define the DP state so that it captures all necessary information to solve the problem optimally.

Approach

We use a 3D DP array dp[l][r][k] where:

  • l and r are the left and right indices of the current subarray.
  • k is the number of boxes of the same color as boxes[r] that are contiguous to the right of r (including boxes[r]). The recurrence is:
  • Remove the last group of k boxes: dp[l][r][k] = dp[l][r-1][0] + (k+1)*(k+1)
  • Try to merge non-contiguous boxes of the same color for higher score.

Recurrence Relation

Let dp(l, r, k) be the maximum score for boxes[l..r] with k boxes of the same color as boxes[r] attached to the right.

  • dp(l, r, k) = dp(l, r-1, 0) + (k+1)*(k+1)
  • For each m in [l, r-1] where boxes[m] == boxes[r], try merging: dp(l, r, k) = max(dp(l, r, k), dp(l, m, k+1) + dp(m+1, r-1, 0))

Base Case

If l > r, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int dp[100][100][100] = {};
    int removeBoxes(vector<int>& boxes) {
        return dfs(boxes, 0, boxes.size() - 1, 0);
    }
    int dfs(vector<int>& boxes, int l, int r, int k) {
        if (l > r) return 0;
        if (dp[l][r][k]) return dp[l][r][k];
        int orig_r = r, orig_k = k;
        while (r > l && boxes[r] == boxes[r-1]) {
            r--, k++;
        }
        dp[l][r][k] = dfs(boxes, l, r-1, 0) + (k+1)*(k+1);
        for (int m = l; m < r; ++m) {
            if (boxes[m] == boxes[r]) {
                dp[l][r][k] = max(dp[l][r][k], dfs(boxes, l, m, k+1) + dfs(boxes, m+1, r-1, 0));
            }
        }
        return dp[l][r][k];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func removeBoxes(boxes []int) int {
    dp := make(map[[3]int]int)
    var dfs func(l, r, k int) int
    dfs = func(l, r, k int) int {
        if l > r {
            return 0
        }
        key := [3]int{l, r, k}
        if v, ok := dp[key]; ok {
            return v
        }
        origR, origK := r, k
        for r > l && boxes[r] == boxes[r-1] {
            r--
            k++
        }
        res := dfs(l, r-1, 0) + (k+1)*(k+1)
        for m := l; m < r; m++ {
            if boxes[m] == boxes[r] {
                res = max(res, dfs(l, m, k+1)+dfs(m+1, r-1, 0))
            }
        }
        dp[key] = res
        return res
    }
    return dfs(0, len(boxes)-1, 0)
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    int[][][] dp;
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        dp = new int[n][n][n];
        return dfs(boxes, 0, n - 1, 0);
    }
    private int dfs(int[] 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] = dfs(boxes, l, r-1, 0) + (k+1)*(k+1);
        for (int m = l; m < r; ++m) {
            if (boxes[m] == boxes[r]) {
                dp[l][r][k] = Math.max(dp[l][r][k], dfs(boxes, l, m, k+1) + dfs(boxes, m+1, r-1, 0));
            }
        }
        return dp[l][r][k];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun removeBoxes(boxes: IntArray): Int {
        val n = boxes.size
        val dp = Array(n) { Array(n) { IntArray(n) } }
        fun dfs(l: Int, r: Int, k: Int): Int {
            if (l > r) return 0
            if (dp[l][r][k] != 0) return dp[l][r][k]
            var rr = r
            var kk = k
            while (rr > l && boxes[rr] == boxes[rr - 1]) {
                rr--
                kk++
            }
            dp[l][rr][kk] = dfs(l, rr - 1, 0) + (kk + 1) * (kk + 1)
            for (m in l until rr) {
                if (boxes[m] == boxes[rr]) {
                    dp[l][rr][kk] = maxOf(dp[l][rr][kk], dfs(l, m, kk + 1) + dfs(m + 1, rr - 1, 0))
                }
            }
            return dp[l][rr][kk]
        }
        return dfs(0, n - 1, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dfs(l, r, k):
            if l > r:
                return 0
            orig_r, orig_k = r, k
            while r > l and boxes[r] == boxes[r-1]:
                r -= 1
                k += 1
            res = dfs(l, r-1, 0) + (k+1)*(k+1)
            for m in range(l, r):
                if boxes[m] == boxes[r]:
                    res = max(res, dfs(l, m, k+1) + dfs(m+1, r-1, 0))
            return res
        return dfs(0, len(boxes)-1, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn remove_boxes(boxes: Vec<i32>) -> i32 {
        fn dfs(boxes: &Vec<i32>, l: usize, r: usize, k: usize, dp: &mut Vec<Vec<Vec<i32>>>) -> i32 {
            if l > r { return 0; }
            if dp[l][r][k] != 0 { return dp[l][r][k]; }
            let mut rr = r;
            let mut kk = k;
            while rr > l && boxes[rr] == boxes[rr - 1] {
                rr -= 1;
                kk += 1;
            }
            dp[l][rr][kk] = dfs(boxes, l, rr - 1, 0, dp) + ((kk + 1) * (kk + 1)) as i32;
            for m in l..rr {
                if boxes[m] == boxes[rr] {
                    dp[l][rr][kk] = dp[l][rr][kk].max(dfs(boxes, l, m, kk + 1, dp) + dfs(boxes, m + 1, rr - 1, 0, dp));
                }
            }
            dp[l][rr][kk]
        }
        let n = boxes.len();
        let mut dp = vec![vec![vec![0; n]; n]; n];
        dfs(&boxes, 0, n - 1, 0, &mut dp)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    removeBoxes(boxes: number[]): number {
        const n = boxes.length;
        const dp: number[][][] = Array.from({ length: n }, () => Array.from({ length: n }, () => Array(n).fill(0)));
        function dfs(l: number, r: number, k: number): number {
            if (l > r) return 0;
            if (dp[l][r][k] !== 0) return dp[l][r][k];
            let rr = r, kk = k;
            while (rr > l && boxes[rr] === boxes[rr - 1]) {
                rr--;
                kk++;
            }
            dp[l][rr][kk] = dfs(l, rr - 1, 0) + (kk + 1) * (kk + 1);
            for (let m = l; m < rr; ++m) {
                if (boxes[m] === boxes[rr]) {
                    dp[l][rr][kk] = Math.max(dp[l][rr][kk], dfs(l, m, kk + 1) + dfs(m + 1, rr - 1, 0));
                }
            }
            return dp[l][rr][kk];
        }
        return dfs(0, n - 1, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(n^4), where n is the number of boxes, due to the 3D DP and possible splits.
  • 🧺 Space complexity: O(n^3), for the DP table.