LC1219. Path with Maximum Gold

Approach 1: Backtracking

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
 
        def dfs(r, c, visited):
            if not (0 <= r < m and 0 <= c < n) or \
               grid[r][c] == 0 or \
               (r, c) in visited:
               return 0
            
            visited.add((r, c))
 
            res = grid[r][c]
 
            for r2, c2 in [
                (r + 1, c),
                (r - 1, c),
                (r, c + 1),
                (r, c - 1)
            ]:
                res = max(res, dfs(r2, c2, visited) + grid[r][c])
 
            visited.remove((r, c))
 
            return res
 
        res = 0
        total_gold = sum(sum(row) for row in grid)
 
        for r in range(m):
            for c in range(n):
                if grid[r][c] != 0:
                    res = max(res, dfs(r, c, set()))
 
                    # Optimization: if we find a path that covers whole grid, exit
                    if res == total_gold:
                        return total_gold
            
        return res

Complexity

Time: $O(mn\cdot 4^{mn})$
Space: $O(m\cdot n)$

Notes

Can optimize space by not using a visited set and instead, setting the cell value to 0 while visiting and reset back to original value before returning from function.

Other Languages