题目描述：

LeetCode 546. Remove Boxes

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 (composed of k boxes, k >= 1), remove them and get `k*k` points.
Find the maximum points you can get.

Example 1:
Input:

```[1, 3, 2, 2, 2, 3, 4, 3, 1]
```

Output:

```23
```

Explanation:

```[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)
```

Note: The number of boxes `n` would not exceed 100.

解题思路：

dp[l][r][k]表示第l到第r个合并后的盒子，连同其后颜色为color[r]的长度k一并消去所能得到的最大得分。

```dp[l][r][k] = dp[l][r - 1][0] + (length[r] + k) ** 2

dp[l][r][k] = max(dp[l][r][k], dp[l][i][length[r] + k] + dp[i + 1][r - 1][0])  其中 i ∈[l, r - 1]```

Python代码：

``````class Solution(object):
def removeBoxes(self, boxes):
"""
:type boxes: List[int]
:rtype: int
"""
self.color, self.length = [], []
for box in boxes:
if self.color and self.color[-1] == box:
self.length[-1] += 1
else:
self.color.append(box)
self.length.append(1)
M, N = len(self.color), len(boxes)
self.dp = [[[0] * N for x in range(M)] for y in range(M)]
return self.solve(0, M - 1, 0)

def solve(self, l, r, k):
if l > r: return 0
if self.dp[l][r][k]: return self.dp[l][r][k]
points = self.solve(l, r - 1, 0) + (self.length[r] + k) ** 2
for i in range(l, r):
if self.color[i] == self.color[r]:
points = max(points, self.solve(l, i, self.length[r] + k) + self.solve(i + 1, r - 1, 0))
self.dp[l][r][k] = points
return points
``````

Pingbacks已关闭。