Remove Boxes Problem

remove-boxes.cs

using System;

class Program {
  public static void Main(string[] args) {
    var test1 = new int[] { 1, 3, 2, 2, 2, 3, 4, 3, 1 };
    var maxPoints = new Solution().RemoveBoxes(test1);
    Console.WriteLine($"Maximum points: {maxPoints}");
  }
}

remove-boxes.md

Remove Boxes Problem

Live Solution on Replit

Explanation

dp[i,j,k] is a max score of subarray b[i] ~ b[j]

if there are k boxes that have the same color as b[j] following b[j]

Those k boxes are from box[j + 1] ~ box[n], to simulate boxes with other colors are removed first.

"ABACA", dp[0,0,2]=dfs("A|AA")=9 # B,C are removed

Base case: if (j > i) then 0

Transition:

dp[i,j,k]=dp[i,j-1,0] + (k + 1)^2 # case 1

dp[i,p,k+1] + dp[p+1,j-1,0] # case 2

Case 1: drop box[j], remove k+1 boxes

Case 2: Try all breakpoints p, attach a[j] to a[p], i <= p < j, box[p] == box[j]

Answer: dp[0,n-1,0]

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

Space complexity: O(n^3)

solution.cs

class Solution {
    private int[][][] dp;
    
    public int RemoveBoxes(int[] boxes) {
        int len = boxes.length;
        dp = new int[len][len][len];
        return dfs(boxes, 0, len - 1, 0);
    }
    
    private int dfs(int[] boxes, int i, int j, int k) {
        if(i > j) return 0;
        if(dp[i][j][k] > 0) return dp[i][j][k];
        dp[i][j][k] = dfs(boxes, i, j - 1, 0) + (k + 1) * (k + 1);
        for(int p = i; p < j; p++) {
            if(boxes[p] == boxes[j]) {
                dp[i][j][k] = Math.max(dp[i][j][k], dfs(boxes, i, p, k + 1) + dfs(boxes, p + 1, j - 1, 0));
            }
        }
        return dp[i][j][k];
    }
}