题目描述
思路解析动画文字版
记住「踩格记金 → 置 0 标记 → 四向取最大 → 退格还原」。下面在官方样例上，从黄金 9 这个起点一步步走。
准备:先看清网格：先扫一遍：网格里一共 5 个有黄金的格(土黄底色，可踩)，写 0 的是空格(灰底，不能进)。题目允许从任意金格出发，所以每个金格都要各当一次起点试一遍。
准备:选一个起点：这里挑收益最高的起点 黄金 9（紫色）演示整条 DFS 搜索，看它一路能挖到多少黄金。
踩进 · 第 1 格：踩进格子 (2,1)，挖到黄金 9：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 9，继续往没踩过的邻居探。
踩进 · 第 2 格：踩进格子 (1,1)，挖到黄金 8：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 17，继续往没踩过的邻居探。
踩进 · 第 3 格：踩进格子 (0,1)，挖到黄金 6：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 23，继续往没踩过的邻居探。
走到头了：格子 (0,1) 的上下左右要么是空格 0、要么已被本趟踩过，无路可走。这条分支到此结束，它能贡献的黄金就是路径上的 6，准备回溯。
回溯:还原这一格：从 (0,1) 退出：把它的金子 6 还原回去（撤销那个置 0 的标记），这样别的走法还能踩到它。退回上一格，继续试它下一个方向。
踩进 · 第 4 格：踩进格子 (1,2)，挖到黄金 7：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 24，继续往没踩过的邻居探。
走到头了：格子 (1,2) 的上下左右要么是空格 0、要么已被本趟踩过，无路可走。这条分支到此结束，它能贡献的黄金就是路径上的 7，准备回溯。
回溯:还原这一格：从 (1,2) 退出：把它的金子 7 还原回去（撤销那个置 0 的标记），这样别的走法还能踩到它。退回上一格，继续试它下一个方向。
踩进 · 第 5 格：踩进格子 (1,0)，挖到黄金 5：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 22，继续往没踩过的邻居探。
走到头了：格子 (1,0) 的上下左右要么是空格 0、要么已被本趟踩过，无路可走。这条分支到此结束，它能贡献的黄金就是路径上的 5，准备回溯。
回溯:还原这一格：从 (1,0) 退出：把它的金子 5 还原回去（撤销那个置 0 的标记），这样别的走法还能踩到它。退回上一格，继续试它下一个方向。
结算:取四向最大：格 (1,1) 的四个方向都试完了，里面最大的一条分支贡献 7。于是本格能挖的黄金 = 自己的 8 + 最大分支 7 = 15，把这个值往上一层返回。
结算:取四向最大：格 (2,1) 的四个方向都试完了，里面最大的一条分支贡献 15。于是本格能挖的黄金 = 自己的 9 + 最大分支 15 = 24，把这个值往上一层返回。
换个起点:从 6 出发：刚才只是其中一个起点。换从顶上的 黄金 6(紫色)出发，把它当起点再跑一遍 DFS，看能不能挖得比 24 更多。
起点 6 · 第 2 格：踩进 (1,1)，挖到黄金 8，这条路累计 14。继续往下探。
起点 6 · 第 3 格：踩进 (2,1)，挖到黄金 9，这条路累计 23。它在底行，四周已经没有能继续接上的金格了，这条路到此为止，准备结算。
起点 6 结算:23：从 6 出发最多挖到 6 + 8 + 9 = 23，比之前从 9 出发的 24 还少 1，所以不刷新答案。这就是「每个金格都当起点、取所有结果最大值」的意义。
搜索结束 · 答案 = 24：从黄金 9 出发的这条线，9 → 8 → 7（绿色）收集到 9 + 8 + 7 = 24 黄金。把每个金格各当起点跑一遍后，没有比它更高的，所以答案是 24。
边界先想清：单格直接收、全空答案 0、连成一条线就全收走。
面试常追问「为什么敢暴力」（看数据范围）和「为什么改原数组而不开 visited」。
参考代码
from typing import Listclass Solution: def getMaximumGold(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(r, c): if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0: return 0 gold = grid[r][c] grid[r][c] = 0 best = max(dfs(r+1,c), dfs(r-1,c), dfs(r,c+1), dfs(r,c-1)) grid[r][c] = gold return gold + best return max(dfs(r, c) for r in range(m) for c in range(n))复杂度
- 时间：O(m·n·4^g)，g = 非零金格数;每个格当起点、每步最多四向延伸
- 空间：O(g)，递归栈深度最多为一条路径的长度 g
易错点
面试追问把动画讲成自己的话
追问这题为什么敢用指数级的回溯，不会超时吗？
追问为什么直接改原网格（置 0 再还原），而不是另开一个 visited 数组？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
串联字符串的最大长度
LeetCode 1239 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题