[Swift]LeetCode546. 移除盒子 | Remove Boxes

发布时间：2020-12-14 05:04:00 所属栏目：百科来源：网络整理

导读：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 (compose

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,4,1]

Output:

Explanation:

[1,1] 
----> [1,1] (3*3=9 points) 
----> [1,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,1]

输出:

解释:

[1,1] (3*3=9 分) 
----> [1,1] (1*1=1 分) 
----> [1,1] (3*3=9 分) 
----> [] (2*2=4 分)

Runtime:?1784 ms

Memory Usage:?21.6 MB

 1 class Solution {
 2     func removeBoxes(_ boxes: [Int]) -> Int {
 3         var n:Int = boxes.count
 4         var dp = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0,count: n),count: n)
 5         for i in 0..<n
 6         {
 7             for k in 0...i
 8             {
 9                 dp[i][i][k] = (1 + k) * (1 + k)
10             }
11         }
12         for t in 1..<n
13         {
14             for j in t..<n
15             {
16                 var i:Int = j - t
17                 for k in 0...i
18                 {
19                     var res:Int = (1 + k) * (1 + k) + dp[i + 1][j][0]
20                     for m in (i + 1)...j
21                     {
22                         if boxes[m] == boxes[i]
23                         {
24                             res = max(res,dp[i + 1][m - 1][0] + dp[m][j][k + 1])
25                         }
26                     }
27                     dp[i][j][k] = res
28                 }
29             }
30         }
31         return n == 0 ? 0 : dp[0][n - 1][0]
32     }
33 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!