{x}
blog image

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

Solution Explanation for Remove Boxes

This problem asks to find the maximum points achievable by removing continuous boxes of the same color. The points gained from removing k boxes of the same color is k*k. A dynamic programming approach with memoization is the most efficient way to solve this.

Approach:

The core idea is to use a 3D DP table dp[i][j][k] where:

  • i: Represents the starting index of the boxes to consider.
  • j: Represents the ending index of the boxes to consider.
  • k: Represents the number of consecutive boxes of the same color as boxes[j] already removed before considering the range [i, j].

The recursive relation is defined as follows:

  1. Base Case: If i > j, there are no boxes left, so return 0.

  2. Merging Consecutive Boxes: If boxes boxes[j] and boxes[j-1] are the same, recursively call the function with j decremented and k incremented, until we encounter a different color or the start index i is reached. This merges consecutive boxes of the same color.

  3. Recursive Step: After merging, we calculate the maximum points that can be obtained as the maximum of the following options:

    • Removing all boxes from i to j-1, then removing boxes j to j (with k+1 already merged boxes of the same type) and obtaining (k+1)*(k+1) points.

    • Iterating over all indices h from i to j-1 where boxes[h] == boxes[j]. For each such h, recursively removing boxes in the range [h+1, j-1] and recursively removing boxes in the range [i, h] with k+1 already merged boxes of the same color. This represents splitting the boxes at index h.

  4. Memoization: Store the result of each subproblem in the dp table to avoid redundant calculations.

Time Complexity: O(n^4), where n is the length of the boxes array. The three nested loops in the recursive solution contribute to the cubic time complexity. The additional iteration within the while loop doesn't affect the overall cubic nature significantly.

Space Complexity: O(n^3) due to the 3D DP table.

Code Implementations:

The code implementations in Python, Java, C++, and Go above demonstrate this dynamic programming approach with memoization. The memoization (using @cache in Python, or manually in other languages) significantly optimizes the runtime by storing and reusing the results of previously computed subproblems. Each implementation follows the recursive steps outlined above, ensuring correctness and efficiency. The max function in the recursive step finds the optimal strategy.