Swift DP Solution


  • 0
    C

    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
    
    

Log in to reply
 

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