Problem statement

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

Solution

Let us reformulate problem: we have two persons, who always go from (0, 0) to (N-1, N-1) and they need to collect as much cherries as possible. Let us use dp (or dfs with memorization), where state is (x1, y1, x2, y2): coordinates of both persons. Note also, that we always have x1 + y1 = x2 + y2, so there will be O(n^3) states.

  1. If we out of grid or we have -1 met, we return minus infinity
  2. if both persons in the start, we return value of this cell.
  3. Now, we have four possible options we can reach our current state: both options (or less if we out of grid) for each person. Also we need to take care of case, where two persons are in one cell, for this we use (grid[x1][y1] + grid[x2][y2])//(1 + (x1 == x2))} trick.

Complexity

Finally, time and space complexity is O(n^3). Space complexity can be reduced to O(n^2).

Code

class Solution:
    def cherryPickup(self, grid):
        N = len(grid)
        def IR(t): return t < 0 or t >= N
        
        @lru_cache(None)
        def dfs(x1, y1, x2, y2):
            if x1 > x2: return dfs(x2, y2, x1, y1)  # optimization, make it twice faster 
            if x1 == y1 == x2 == y2 == 0: return grid[0][0]
            if grid[x1][y1] == -1 or grid[x2][y2] == -1: return -float("inf")
            if IR(x1) or IR(x2) or IR(y1) or IR(y2): return -float("inf")
           
            cand_next = []
            for i1, j1 in [(x1, y1-1), (x1-1, y1)]:
                for i2, j2 in  [(x2, y2-1), (x2-1, y2)]:
                    cand_next.append(dfs(i1, j1, i2, j2))
            return max(cand_next) + (grid[x1][y1] + grid[x2][y2])//(1 + (x1 == x2))
                    
        res = dfs(N-1, N-1, N-1, N-1)
        return res if res != -float("inf") else 0