Remove Boxes - 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. Find the maximum points you can get.

Solution Approach:

This problem belongs to dynamic programming and to understand the nature of the problem clearly, let us consider a few test cases: 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] (33=9 points) ----> [1, 3, 3, 3, 1] (11=1 points) ----> [1, 1] (33=9 points) ----> [] (22=4 points) Thus, totally 9 + 1 + 9 + 4 = 23 points

Example 2:

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

Input: boxes = [1,1] Output: 4 Example 5:

Input: boxes = [1] Output: 1 From the above examples, we can conclude that the order of removing the boxes is important.

Hence, our goal here is to create a recursive scheme that will remove the boxes in such a way as to maximize the points earned. As we develop the recursive algorithm, we will note that the number of boxes is important so we will include it as a variable i. Since we aim to maximize the number of points, we will keep track of the points earned parameterized by i in order to return the maximum possible points.

The first step is to define the base cases. Here, the base cases should occur when there are less than two boxes and should only return i*i.

Next, for each box in the input array, we will consider consecutive segments with the same color. When we find a segment, we will provide that segment as input to the recursive definition while keeping track of the maximum points earned. We will then return the maximum points earned.

Now, if we have processed the entire array, the maximum points would have been obtained. We will return the maximum points.

Code: Let us now implement the above approach through code.

    def removeBoxes(self, boxes: List[int]) -> int:
    
        memo = {}
    
        def dp(i, j, k):
            
            if i > j: return 0
            
            if (i, j, k) in memo:
                return memo[(i, j, k)]
            
            # If we have consecutive boxes of the same color, increase k
            nonlocal boxes
            while i < j and boxes[j] == boxes[j-1]:
                j -= 1
                k += 1
            
            # Case 1: Remove box[j] separately before the last box so that the last box can be matched with adjacent boxes
            ans = dp(i, j-1, 0) + (k+1)*(k+1)
            
            # Case 2: Match box[j] with an adjacent box that is not the last box
            for m in range(i, j):
                if boxes[m] == boxes[j]:
                    ans = max(ans, dp(i, m, k+1) + dp(m+1, j-1, 0))
            
            memo[(i, j, k)] = ans
            
            return ans

        return dp(0, len(boxes)-1, 0)

1