Let A be the array of boxes.
One natural approach is to consider dp(i, j) = the answer for A[i: j+1]. But this isn't flexible enough for divide and conquer style strategies. For example, with [1,2,2,2,1], we don't have enough information when investigating things like [1,2,2,2] and  separately.
Let dp(i, j, k) = the maximum value of removing boxes if we have k extra boxes of color A[i] to the left of A[i: j+1]. (We would have at most k < len(A) extra boxes.) Let m <= j be the largest value so that A[i], A[i+1], ... A[m] are all the same color. Because a^2 + b^2 < (a+b)^2, any block of contiguous boxes of the same color must be removed at the same time, so in fact dp(i, j, k) = dp(m, j, k+(m-i)).
Now, we could remove the k boxes we were carrying plus box A[i] (value: (k+1)**2), then remove the rest (value: dp(i+1, j, 0)). Or, for any point m in [i+1, j] with A[i] == A[m], we could remove dp(i+1, m-1) first, then [m, j] would have k+1 extra boxes of color A[m] behind, which has value dp(m, j, k+1).
The "i, k = m, k + m - i" part skips order (m-i)*(j-i) calls to dp, and is necessary to get this kind of solution to pass in Python.
def removeBoxes(self, A): N = len(A) memo = [[*N for _ in xrange(N) ] for _ in xrange(N) ] def dp(i, j, k): if i > j: return 0 if not memo[i][j][k]: m = i while m+1 <= j and A[m+1] == A[i]: m += 1 i, k = m, k + m - i ans = dp(i+1, j, 0) + (k+1) ** 2 for m in xrange(i+1, j+1): if A[i] == A[m]: ans = max(ans, dp(i+1, m-1, 0) + dp(m, j, k+1)) memo[i][j][k] = ans return memo[i][j][k] return dp(0, N-1, 0)
dp(i, j, k) = dp(m, j, k+(m-i))
how did you arrive at k+m-i number there?
@sha256pki he defines k as # of boxes that are == A[i]. Since m represents how many identical boxes we have at the beginning of the region from i to j, dp for region m to j would have k + (m-i) boxes to the left. Note that it's m-i because i might not be 0.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.