题目描述：

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.

题目大意：

给定一些不同颜色的盒子，以不同的正整数表示。

消去连续相同颜色的盒子，直到全部消除完毕为止。每一次消去可以得到k * k分（k为消去盒子的个数， k  >= 1）。

计算可以得到的最大得分。

注意：盒子的数量n不超过100。

解题思路：

动态规划（Dynamic Programming）

首先把连续相同颜色的盒子进行合并，得到数组color以及数组length，分别表示合并后盒子的颜色和长度。

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

 

本文链接：http://bookshadow.com/weblog/2017/03/26/leetcode-remove-boxes/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码