python DP with memoization and optimization

  • 0

    Inspired by @fun4LeetCode

    class Solution(object):
        def removeBoxes(self, boxes):
            :type boxes: List[int]
            :rtype: int
            self.boxes = boxes
            n = len(boxes)
            self._cache = [[[None]*n for _ in range(n)] for _ in range(n)]
            return self.dp(0, n-1, 0)
        def dp(self, i, j, k):
            Let, `F(i,j,k)` be the sub-problem which assigns Maximum points by removing `boxes[i..j]` and `k` is the number of `boxes[i]` to the left of `i`.
            Original Problem:  
            `F(0,n-1,0)` since no boxes attached to left of input.  
            Termination conditions:  
            `F(i, i-1, k) = 0` Value of `k` does not matter.  
            `F(i, i, k) = (k+1)*(k+1)` `k boxes[i]` before i and `boxes[i]` can be combined and removed.  
            1. removing `boxes[i]` would result in: `F(i,j,k) = F(i+1,j,0) + (k+1)*(k+1)`
            2. folding `boxes[m]` into `k` would result in: `F(i,j,k) = F(i+1, m-1, 0) + F(m, j, k+1)`
            3. generalizing 2, `F(i,j,k) = max(F(i+1, m-1, 0) + F(m,j,k+1)) where i<m<=j && boxes[i]==boxes[m]` 
            if j < i: return 0
            if j == i: return (k+1)*(k+1)
            if self._cache[i][j][k]: return self._cache[i][j][k]
            # optimize repeated values at the begining
            _m = i
            while(_m<j and self.boxes[_m+1] == self.boxes[i]): _m+=1
            k += _m-i
            i = _m
            rv = max([self.dp(i+1, m-1, 0) + self.dp(m,j,k+1) for m in xrange(i+1, j+1) if self.boxes[i]==self.boxes[m]] + [(k+1)*(k+1)+self.dp(i+1, j, 0)])
            self._cache[i][j][k] = rv
            return self._cache[i][j][k]

Log in to reply

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