# Swift DP Solution

• DP Solution

dp[l][r][k] means from left to right take k boxes with the color same as boxes[l]

``````class Solution {

var dp: [[[Int]]] = Array(repeatElement(Array(repeatElement(Array(repeatElement(-1,count:110)),count:110)),count:110))
var boxes: [Int] = [0]
var n = 0

func removeBoxes(_ boxes: [Int]) -> Int {
self.n = boxes.count
self.boxes = boxes
self.dp = Array(repeatElement(Array(repeatElement(Array(repeatElement(-1,count:110)),count:110)),count:110))
let ans = dfs(0,n-1,1)
return ans
}

func dfs(_ l:Int ,_ r:Int ,_ k:Int) -> Int {

if l > r {
return 0
}

if l == r {
return k*k;
}

if dp[l][r][k] != -1 {
return dp[l][r][k]
}

var nl = l+1
var nk = k
while nl<r && boxes[nl]==boxes[l] {
nl += 1
nk += 1
}

dp[l][r][k] = max(dp[l][r][k],dfs(nl,r,1)+nk*nk)

for i in nl...r {
if boxes[i] == boxes[l] {
dp[l][r][k] = max(dp[l][r][k],dfs(i,r,nk+1)+dfs(nl,i-1,1))
}
}

return dp[l][r][k]
}
}
var s = Solution()

print(s.removeBoxes([1,3,2,2,2,3,4,3,1])) // 23
print(s.removeBoxes([1,1,1,1,2])) // 17
print(s.removeBoxes([1,1,1,1,1])) // 25
print(s.removeBoxes([2,5,10,9,4,8,6,9,9,1])) // 16

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.