Remove Boxes — LeetCode 546 Python Solution

The 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.

Example

Input

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

Output

23

Explanation

[1, 3, 2, 2, 2, 3, 4, 3, 1]

Python solution

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def dfs(i, j, k):
            if i > j:
                return 0
            while i < j and boxes[j] == boxes[j - 1]:
                j, k = j - 1, k + 1
            ans = dfs(i, j - 1, 0) + (k + 1) * (k + 1)
            for h in range(i, j):
                if boxes[h] == boxes[j]:
                    ans = max(ans, dfs(h + 1, j - 1, 0) + dfs(i, h, k + 1))
            return ans

        n = len(boxes)
        ans = dfs(0, n - 1, 0)
        dfs.cache_clear()
        return ans

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 546. Remove Boxes is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming and Memoization.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems