# python DP with memoization and optimization

• 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.

Recurrance:
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]

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