We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Boxes

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem involves dynamic programming to maximize the score from removing boxes.
  • The main challenge is to consider both the number of boxes and the colors of adjacent boxes.
  • We can benefit from memoization to avoid redundant calculations when checking different combinations of boxes to remove.

Space and Time Complexity

Time Complexity: O(N^3)
Space Complexity: O(N^3)

Solution

The problem can be solved using a dynamic programming approach. We define a 3D DP array dp[l][r][k] where:

  • l is the left index of the current segment of boxes.
  • r is the right index of the current segment of boxes.
  • k is the number of boxes with the same color as the box at index r that are adjacent to r.

The idea is to calculate the maximum points by considering:

  1. Removing boxes in the range [l, r] directly.
  2. Merging the segments optimally by exploring all possible divisions of the segment.

We recursively compute the maximum points for every possible combination of left and right indices and store the results in the DP table to avoid redundant calculations.

Code Solutions

def removeBoxes(boxes):
    n = len(boxes)
    dp = [[[0] * (n + 1) for _ in range(n)] for _ in range(n)]

    def dfs(l, r, k):
        if l > r: 
            return 0
        if dp[l][r][k]: 
            return dp[l][r][k]

        while r > l and boxes[r] == boxes[r - 1]:
            r -= 1
            k += 1
        
        dp[l][r][k] = dfs(l, r - 1, 0) + (k + 1) * (k + 1)

        for m in range(l, r):
            if boxes[m] == boxes[r]:
                dp[l][r][k] = max(dp[l][r][k], dfs(l, m, k + 1) + dfs(m + 1, r - 1, 0))

        return dp[l][r][k]

    return dfs(0, n - 1, 0)
← Back to All Questions