Problem statement

https://binarysearch.com/problems/Collecting-Coins-Trequel/

Solution

Variation of Leetcode 0741. Cherry Pickup, be careful with dimensions, also if (0, 0) cell is equal to -1, we can return 0.

Complexity

It is O(mn(m+n)) for time and space.

Code

class Solution:
    def solve(self, grid):
        n, m = len(grid), len(grid[0])
        INF = -float("inf")
        
        @lru_cache(None)
        def dfs(x1, y1, x2, y2):
            if x1 == y1 == x2 == y2 == 0: return grid[0][0] if grid[0][0] != -1 else INF
            if not 0 <= x1 < n or not 0 <= x2 < n: return INF
            if not 0 <= y1 < m or not 0 <= y2 < m: return INF
            if grid[x1][y1] == -1 or grid[x2][y2] == -1: return 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, m-1, n-1, m-1)
        return res if res != INF else 0