1463. Cherry Pickup II

https://leetcode.com/problems/cherry-pickup-ii/

Top Down Dp

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        self.cache = dict()
        def dp(row,col1,col2):
            if row >= m:
                return 0
            if (row,col1,col2) in self.cache:
                return self.cache[(row,col1,col2)]
            curr = 0
            res = 0
            if col1 == col2:
                curr += grid[row][col1]
            else:
                curr += grid[row][col1] + grid[row][col2]
            for i in range(-1,2):
                for j in range(-1,2):
                    newCol1 = col1 + i
                    newCol2 = col2 + j
                    if 0 <= newCol1 < n and 0 <= newCol2 < n:
                        res = max(res,curr + dp(row+1,newCol1,newCol2))
            self.cache[(row,col1,col2)] = res
            return res
        return dp(0,0,n-1)