难度: Hard
给出一些不同颜色的盒子 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 <= 1001 <= boxes[i] <= 100运行时间: 416 ms
内存: 0.0 MB
class Solution:
def removeBoxes(self, boxes):
"""
:type boxes: List[int]
:rtype: int
"""
# Let A be the array of boxes.
# One natural approach is to consider dp(i, j) = the answer for A[i: j+1]. But this isn't flexible enough for divide and conquer style strategies. For example, with [1,2,2,2,1], we don't have enough information when investigating things like [1,2,2,2] and [1] separately.
# Let dp(i, j, k) = the maximum value of removing boxes if we have k extra boxes of color A[i] to the left of A[i: j+1]. (We would have at most k < len(A) extra boxes.) Let m <= j be the largest value so that A[i], A[i+1], ... A[m] are all the same color. Because a^2 + b^2 < (a+b)^2, any block of contiguous boxes of the same color must be removed at the same time, so in fact dp(i, j, k) = dp(m, j, k+(m-i)).
# Now, we could remove the k boxes we were carrying plus box A[i] (value: (k+1)**2), then remove the rest (value: dp(i+1, j, 0)). Or, for any point m in [i+1, j] with A[i] == A[m], we could remove dp(i+1, m-1) first, then [m, j] would have k+1 extra boxes of color A[m] behind, which has value dp(m, j, k+1).
# The "i, k = m, k + m - i" part skips order (m-i)*(j-i) calls to dp, and is necessary to get this kind of solution to pass in Python.
N = len(boxes)
memo = [[[0] * N for _ in range(N) ] for _ in range(N)]
def dp(i, j, k):
if i > j:
return 0
if not memo[i][j][k]:
index = i
while index + 1 <= j and boxes[index + 1] == boxes[i]:
index += 1
k = k + index - i
i = index
ans = dp(i + 1, j, 0) + (k + 1) ** 2
for index in range(i + 1, j + 1):
if boxes[i] == boxes[index]:
ans = max(ans, dp(i + 1, index - 1, 0) + dp(index, j, k + 1))
memo[i][j][k] = ans
return memo[i][j][k]
return dp(0, N - 1, 0)
这个题解使用了动态规划的思路。定义状态 dp(i, j, k) 表示考虑区间 [i, j] 中的盒子，并且区间外有 k 个颜色与 boxes[i] 相同的盒子时，能获得的最大积分。状态转移时，可以选择先移除区间 [i, i] 的盒子，获得 (k+1)^2 的积分，再去求解子问题 dp(i+1, j, 0)。也可以选择先移除中间某个位置 m 的盒子（boxes[m] == boxes[i]），获得 dp(i+1, m-1, 0) 的积分，再去求解子问题 dp(m, j, k+1)。在这两种决策中取较大值即可。
时间复杂度: O(n^3)
空间复杂度: O(n^3)
class Solution:
def removeBoxes(self, boxes):
"""
:type boxes: List[int]
:rtype: int
"""
N = len(boxes)
memo = [[[0] * N for _ in range(N) ] for _ in range(N)]
def dp(i, j, k):
if i > j:
return 0
if not memo[i][j][k]:
# 找到第一个与 boxes[i] 颜色不同的盒子位置
index = i
while index + 1 <= j and boxes[index + 1] == boxes[i]:
index += 1
# 更新状态，将与 boxes[i] 颜色相同的盒子数量并入 k
k = k + index - i
i = index
# 决策1：移除区间 [i, i] 的盒子，获得 (k+1)^2 的积分，然后求解子问题 dp(i+1, j, 0)
ans = dp(i + 1, j, 0) + (k + 1) ** 2
# 决策2：先移除中间某个位置 m 的盒子，获得 dp(i+1, m-1, 0) 的积分，然后求解子问题 dp(m, j, k+1)
for index in range(i + 1, j + 1):
if boxes[i] == boxes[index]:
ans = max(ans, dp(i + 1, index - 1, 0) + dp(index, j, k + 1))
memo[i][j][k] = ans
return memo[i][j][k]
return dp(0, N - 1, 0)
在这个问题中，包含参数k是因为盒子移除时的得分不仅依赖于当前区间内的盒子数量和颜色，还显著依赖于紧邻该区间外与boxes[i]相同颜色的盒子数量。这是因为当存在外部相同颜色的盒子时，一并移除可以获得更高的分数，因为分数是基于相同颜色盒子连续移除数量的平方来计算的，所以k极大地影响了策略和得分。参数k使得状态能够精确地描述和利用这一得分机制。
选择加上(k+1)^2是因为题目规定移除连续相同颜色的盒子可以获得的分数是连续盒子数量的平方。这里k代表在i之前已经累积的与boxes[i]相同颜色的盒子数量，因此当移除从i开始的k+1个相同颜色盒子时，其对应的得分自然应该是(k+1)^2。这种得分机制是题目设定的核心规则，直接影响到最终的最大分数计算。
这种处理方式实际上是基于贪心策略，先尽可能合并连续的同色盒子以获得更高的平方分数。此方法不会忽略最优解，因为通过动态规划的其他部分（即决策2），算法仍然会考虑在后续位置重新分割和评估这些盒子，从而确保每种可能的分割方式都被考虑到。这种方法是为了减少重复计算并优化计算过程，而不是简单地忽略某些情况。
最优的分割点m是通过遍历所有可能的m位置并计算相应的分数来确定的。对于每一个可能的位置m（其中boxes[m]与boxes[i]颜色相同），算法会计算两部分：一部分是移除从i+1到m-1的所有盒子后的得分，另一部分是考虑从m开始、考虑到外部相同颜色盒子k+1的情形下，到j为止的得分。通过比较所有这些可能分割点m的得分，选择能够产生最大总得分的m。这种方法确保了每一种可能的分割都被考虑到，因此能够确保找到最优解。