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.

#546

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

移除盒子

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（ k >= 1 ），这样一轮之后你将得到 k * k 个积分。返回你能获得的最大积分和。示例 1：输入： boxes …

数组动态规划记忆化

题目描述

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。

返回 你能获得的最大积分和 。

示例 1：

输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)

示例 2：

输入：boxes = [1,1,1]
输出：9

示例 3：

输入：boxes = [1]
输出：1

提示：

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

lightbulb

解题思路

方法一：记忆化搜索

设计递归函数 dfs(i, j, k) 表示当前处理的区间为 [i, j]，且该区间的右边有 k 个与 boxes[j] 相同的元素，返回该区间的最大积分。答案即为 dfs(0, n - 1, 0)。

对于 dfs(i, j, k)，我们可以直接删除 boxes[j] 和其右边的 k 个元素，所得积分为 dfs(i, j - 1, 0) + (k + 1) * (k + 1)。

我们还可以在区间 [i, j-1] 内枚举下标 h，找到满足 boxes[h] == boxes[j] 的下标，那么我们就将区间 [i, j - 1] 分成两部分，即 [i, h] 和 [h + 1, j - 1]。其中 [i, h] 的部分可以与 boxes[j] 合并，所以积分为 dfs(i, h, k + 1) + dfs(h + 1, j - 1, 0)。求不同 h 下的最大值即可。

我们使用记忆化搜索来优化递归函数的时间复杂度。

时间复杂度 $O(n^4)$ ，空间复杂度 $O(n^3)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#638 大礼包 #691 贴纸拼词 #698 划分为k个相等的子集