LeetCode 546: Remove Boxes

Explanation

The given problem can be solved using dynamic programming. We can define a function dp(i, j, k) that represents the maximum points that can be obtained by removing boxes from index i to index j while having k boxes of the same color as box i appended at the end. The key insight is to consider the possibilities of different cases when removing boxes.

1. If the k boxes are attached to box i, we can remove them at the same time to get k*k points plus the maximum points from dp(i+1, j, 1).
2. For each middle box m between i and j, if box i and m have the same color, we can consider the possibility of removing box i later after removing boxes from m+1 to j to get more points.
3. For the case where there is no box with the same color as box i, we can simply remove box i and its adjacent boxes from i+1 to j first to get dp(i+1, j, 1) points.

By considering all these possibilities, we can build our dynamic programming solution to find the maximum points.

Time complexity: O(n^4)
Space complexity: O(n^3)

class Solution {
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        int[][][] dp = new int[n][n][n];
        return calculatePoints(boxes, dp, 0, n - 1, 0);
    }

    private int calculatePoints(int[] boxes, int[][][] dp, int i, int j, int k) {
        if (i > j) return 0;
        if (dp[i][j][k] != 0) return dp[i][j][k];

        while (i + 1 <= j && boxes[i] == boxes[i + 1]) {
            i++;
            k++;
        }
        
        int points = (k + 1) * (k + 1) + calculatePoints(boxes, dp, i + 1, j, 0);

        for (int m = i + 1; m <= j; m++) {
            if (boxes[i] == boxes[m]) {
                points = Math.max(points, calculatePoints(boxes, dp, i + 1, m - 1, 0) + calculatePoints(boxes, dp, m, j, k + 1));
            }
        }

        dp[i][j][k] = points;
        return points;
    }
}