#546

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Remove Boxes

Maximize points by strategically removing contiguous same-colored boxes using state transition dynamic programming and memoization.

array dynamic programming memoization

Problem Statement

You are given an array of boxes, each represented by a positive integer indicating its color. You can remove consecutive boxes of the same color in a single move, scoring points equal to the square of the number of boxes removed in that move.

Your task is to return the maximum points obtainable by removing all boxes in an optimal sequence. Each removal may alter the array structure, requiring careful planning of future moves using dynamic programming and memoization to track overlapping subproblems.

Examples

Example 1

Input: boxes = [1,3,2,2,2,3,4,3,1]

Output: 23

[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 details omitted.

Example 3

Input: boxes = [1]

Output: 1

Example details omitted.

Constraints

1 <= boxes.length <= 100
1 <= boxes[i] <= 100

Solution Approach

Recursive DP with 3D memoization

Define a function dp(l, r, k) representing the maximum points for subarray boxes[l..r] with k contiguous boxes equal to boxes[r] appended. Recursively compute by removing boxes[r] with its k count, then explore merging non-contiguous same-colored blocks for higher points.

State transition strategy

Iterate through the subarray to identify positions where boxes match boxes[r]. Instead of removing immediately, consider skipping some to merge with future identical boxes. Update dp[l][r][k] by comparing direct removal versus merged removal, capturing optimal transitions.

Memoization to avoid recomputation

Store all dp[l][r][k] results in a 3D array. Without memoization, overlapping subproblems explode exponentially. Using this memoized DP ensures each unique state is computed once, significantly reducing time complexity and making the solution tractable for up to 100 boxes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is approximately O(n^4) in the worst case due to three nested loops plus recursive calls, but memoization prunes repeated states. Space complexity is O(n^3) to store dp[l][r][k] for all subarray ranges and contiguous counts.

What Interviewers Usually Probe

Asks about dynamic programming state representation with extra parameters.
Tests if candidate can correctly implement 3D memoization to prevent recomputation.
May probe on optimization strategies when merging non-contiguous same-colored blocks.

Common Pitfalls or Variants

Common pitfalls

Forgetting to carry contiguous count k, leading to suboptimal scoring.
Attempting purely iterative DP without handling merging, which misses higher point combinations.
Overlooking memoization, causing exponential time and timeout for larger arrays.

Follow-up variants

Limit points to removing only pairs of boxes instead of k-length sequences.
Introduce a cost for each removal, changing the scoring function.
Allow only removing boxes from either end, turning it into a simplified interval DP problem.

FAQ

What is the main pattern used in Remove Boxes?

The main pattern is state transition dynamic programming with memoization, tracking contiguous same-colored boxes to maximize points.

Why do we need a 3D DP array?

The 3D DP stores subarray indices and the count of contiguous boxes of the same color to capture all optimal removal sequences efficiently.

Can Remove Boxes be solved iteratively?

Purely iterative approaches are possible but tricky; handling merging of non-contiguous same-colored blocks is more straightforward with recursive memoization.

What is the expected time complexity for Remove Boxes?

With memoization, the worst-case time complexity is around O(n^4), and space complexity is O(n^3) for storing dp states.

How does GhostInterview help with Remove Boxes?

It guides on recursive state transitions, memoization setup, and merging strategies to implement the solution correctly and efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def dfs(i, j, k):
            if i > j:
                return 0
            while i < j and boxes[j] == boxes[j - 1]:
                j, k = j - 1, k + 1
            ans = dfs(i, j - 1, 0) + (k + 1) * (k + 1)
            for h in range(i, j):
                if boxes[h] == boxes[j]:
                    ans = max(ans, dfs(h + 1, j - 1, 0) + dfs(i, h, k + 1))
            return ans

        n = len(boxes)
        ans = dfs(0, n - 1, 0)
        dfs.cache_clear()
        return ans

Continue Practicing

#638 shopping offers #691 stickers to spell word #698 partition to k equal sum subsets