Leetcode 546 Solution
This article provides solution to leetcode question 546 (remove-boxes)
Access this page by simply typing in "lcs 546" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
https://leetcode.com/problems/remove-boxes
Solution
class Solution:
def removeBoxes(self, boxes: List[int]) -> int:
self.m = {}
def dfs(i, j, k, boxes):
if i > j:
return 0
key = (i, j, k)
if key in self.m:
return self.m[key]
ans = (k + 1) * (k + 1) + dfs(i + 1, j, 0, boxes)
l = i + 1
while l <= j:
while l <= j and boxes[i] != boxes[l]:
l += 1
r = l
while r < j and boxes[i] == boxes[r + 1]:
r += 1
if l <= j:
ans = max(ans, dfs(i + 1, l - 1, 0, boxes) + dfs(r, j, k + 1 + r - l, boxes))
l = r + 1
self.m[key] = ans
return ans
return dfs(0, len(boxes) - 1, 0, boxes)