Remove Boxes

Problem Statement

In the given task, you have a list of "boxes" where each box is represented by a positive number that denotes its color. You can remove boxes from this list through several rounds based on specific rules to earn points. In each round, you may choose any series of consecutive boxes with identical color values. The points you score from removing these boxes are calculated as the square of the number of boxes removed (i.e., (k) boxes removed gives you (k \times k) points). The challenge is to devise a strategy that maximizes the total points earned by the time all boxes have been removed from the list.

Examples

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

Approach and Intuition

1. Understanding the Problem Through Examples:

   • Take example 1 with boxes = [1,3,2,2,2,3,4,3,1], removing three consecutive boxes of color '2' first achieves 9 points. The sequence after several optimal removals gives total points of 23. Understanding how to maximize the point from each removal is crucial.
   • From example 2 (boxes = [1,1,1]), simply removing all three boxes at once, as they are the same color, gives (3 \times 3 = 9) points, which is the maximum possible for this scenario.
   • Example 3, with a single box (boxes = [1]), shows the simplest case with a score of (1 \times 1 = 1).

2. Breaking Down the Problem:

   • Dynamic Programming: Given the constraints (maximum length of 100), a brute force approach trying every possible combination of removals would be inefficient. A dynamic programming solution helps break down the problem by reusing solutions to subproblems.
   • Recursive Relations: At each step, consider:
     • The immediate score from removing a segment of boxes.
     • The maximum score obtainable from the remaining segments. This recursive aspect demands memoization or storing intermediate results to avoid recalculations.

3. Memoization Layer:

   • Introduce a 3D memoization array where dp[l][r][k] captures the max points from index l to r in the boxes array, with k extra boxes of boxes[r] color attached hypothetically to the right of r. This handles cases where combining future like-colored segments maximizes points.

4. Iterative Process through Example Walkthrough:

   • Continuing with example 1:
     • Start by evaluating smaller segments and grow to include larger segments,
     • Calculate the combined score of removing chunks versus splitting them to potentially merge with future like-colored segments.
   • Evaluate all strategies for each segment and choose the maximum achievable score using previously computed results.

By applying dynamic programming, the algorithm efficiently computes the maximum score, considering both immediate benefits and future potential profits through strategic box removals. This method ensures that all potential scenarios are considered without recalculating the results of previously evaluated segments.

Solutions

class Solution {
    public int maximizePoints(int[] blocks) {
        int[][][] memo = new int[100][100][100];
        return computeScore(blocks, memo, 0, blocks.length - 1, 0);
    }
    
    private int computeScore(int[] blocks, int[][][] memo, int start, int end, int repetitions) {
        if (start > end) {
            return 0;
        }
        
        while (end > start && blocks[end] == blocks[end - 1]) {
            end--;
            repetitions++;
        }
        
        if (memo[start][end][repetitions] != 0) {
            return memo[start][end][repetitions];
        }
        
        memo[start][end][repetitions] = computeScore(blocks, memo, start, end - 1, 0) + (repetitions + 1) * (repetitions + 1);
        for (int i = start; i < end; i++) {
            if (blocks[i] == blocks[end]) {
                memo[start][end][repetitions] = Math.max(memo[start][end][repetitions], computeScore(blocks, memo, start, i, repetitions + 1)
                                                       + computeScore(blocks, memo, i + 1, end - 1, 0));
            }
        }
                              
        return memo[start][end][repetitions];
    }
}