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 >= 1), 这样一轮之后你将得到 k*k 个积分.
当你将所有盒子都去掉之后, 求你能获得的最大积分和.
示例 1:
输入:
[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 分)
- Runtime: 1784 ms
- Memory Usage: 21.6 MB
- class Solution {
- func removeBoxes(_ boxes: [Int]) -> Int {
- var n:Int = boxes.count
- var dp = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: n), count: n), count: n)
- for i in 0..<n
- {
- for k in 0...i
- {
- dp[i][i][k] = (1 + k) * (1 + k)
- }
- }
- for t in 1..<n
- {
- for j in t..<n
- {
- var i:Int = j - t
- for k in 0...i
- {
- var res:Int = (1 + k) * (1 + k) + dp[i + 1][j][0]
- for m in (i + 1)...j
- {
- if boxes[m] == boxes[i]
- {
- res = max(res, dp[i + 1][m - 1][0] + dp[m][j][k + 1])
- }
- }
- dp[i][j][k] = res
- }
- }
- }
- return n == 0 ? 0 : dp[0][n - 1][0]
- }
- }
[Swift]LeetCode546. 移除盒子 | Remove Boxes
来源: http://www.bubuko.com/infodetail-2962184.html