- 标签:记忆化搜索、数组、动态规划
- 难度:困难
描述:给定一个代表不同颜色盒子的正数数组
我们将经过若干轮操作去去掉盒子,直到所有盒子都去掉为止。每一轮我们可以移除具有相同颜色的连续
要求:返回我们能获得的最大积分和。
说明:
-
$1 \le boxes.length \le 100$ 。 -
$1 \le boxes[i] \le 100$ 。
示例:
- 示例 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
对于每个盒子,
如果使用二维状态
因此,我们需要再二维状态的基础上,增加更多维数的状态。
对于当前区间
按照区间长度进行阶段划分。
定义状态
- 当区间长度为
$1$ 时,当前区间只有一个盒子,区间末尾有$k$ 个与$boxes[j]$ 颜色相同的盒子,所能够得到的最大积分为$(k + 1) \times (k + 1)$ 。 - 当区间长度大于
$1$ 时,对于区间末尾的$k$ 个与$boxes[j]$ 颜色相同的盒子,有两种处理方式:- 将末尾的盒子移除,所能够得到的最大积分为:移除末尾盒子之前能够获得的最大积分和,再加上本轮移除末尾盒子能够获得的积分和,即:$dp[i][j - 1][0] + (k + 1) \times (k + 1)$。
- 在区间中找到一个位置
$t$ ,使得第$t$ 个盒子与第$j$ 个盒子颜色相同,先将区间$[t + 1, j - 1]$ 的盒子消除,然后继续凑同色盒子,即:$dp[t + 1][j - 1][0] + dp[i][t][k + 1]$。
- 区间长度为
$1$ 时,当前区间只有一个盒子,区间末尾有$k$ 个与$boxes[j]$ 颜色相同的盒子,所能够得到的最大积分为$(k + 1) \times (k + 1)$ 。
根据我们之前定义的状态,$dp[i][j][k]$ 表示为:移除区间
class Solution:
def removeBoxes(self, boxes: List[int]) -> int:
size = len(boxes)
dp = [[[0 for _ in range(size)] for _ in range(size)] for _ in range(size)]
for l in range(1, size + 1):
for i in range(size):
j = i + l - 1
if j >= size:
break
for k in range(size - j):
if l == 1:
dp[i][j][k] = max(dp[i][j][k], (k + 1) * (k + 1))
else:
dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][0] + (k + 1) * (k + 1))
for t in range(i, j):
if boxes[t] == boxes[j]:
dp[i][j][k] = max(dp[i][j][k], dp[t + 1][j - 1][0] + dp[i][t][k + 1])
return dp[0][size - 1][0]
-
时间复杂度:$O(n^4)$,其中
$n$ 为数组$boxes$ 的元素个数。 - 空间复杂度:$O(n^3)$。