发表于 2024.07.09

• 此类问题均可考虑使用DFS+回溯法解决。在这道题中，以每一个有黄金的点为起点，进行深度优先搜索，找到最大的路径和。在搜索过程中，由于不允许回到已经开采的点，需要记录已经访问过的点，以避免重复访问。有一个节省空间的trick，即在访问过一个点后，将其值置为0，这样就不需要额外的空间记录已经访问过的点，待回溯结束后，将其值恢复即可。

  上述节省空间的trick可以更形象地理解为，将已经访问过的点视为已经开采过的金矿，将其值置为0，表示此点无矿，不能再次访问。在回溯结束后，将其值恢复，表示金矿又重新出现，可以再次开采。

  class Solution:
      moves = ((-1, 0), (1, 0), (0, -1), (0, 1))
  
      def getMaximumGold(self, grid: List[List[int]]) -> int:
          ans = 0
          m, n = len(grid), len(grid[0])
  
          def dfs(r: int, c: int, val: int):
              nonlocal ans
              ans = max(ans, val)
              orig = grid[r][c]
              grid[r][c] = 0
  
              for move in self.moves:
                  nr = r + move[0]
                  nc = c + move[1]
                  if 0 <= nr < m and 0 <= nc < n and grid[nr][nc]:
                      dfs(nr, nc, val + grid[nr][nc])
  
              grid[r][c] = orig
  
          for i in range(m):
              for j in range(n):
                  if grid[i][j]:
                      dfs(i, j, grid[i][j])
          return ans

• LC 题目链接