LeetCode 1219. 黄金矿工

2023-09-07 HGNULB 约 12 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1219. 黄金矿工

题意分析

在一个 m × n 的网格里，每格写着这里有多少黄金，0 表示没有。可以从任意一个有黄金的格子出发，每步走到上下左右相邻的格子，规则有三条：不能走进值为 0 的格子（也不能借道穿过它），同一条路径里每个格子只能走一次，随时可以停下。求一条路径能收集到的黄金总和的最大值。

先辨认这是不是动态规划。DP 要求子问题的解只依赖「当前位置」这类少量状态，但这里的可行走法依赖整条已走路径——同一个格子在不同路径下能否再进取决于之前有没有踩过它。状态里必须携带访问集合，格子数一多就爆炸，所以 DP 这条路被堵死了。「路径不能自交 + 求最优路径」几乎总是指向搜索。

再看约束是否允许指数级搜索。网格最大 15 × 15，看起来有 225 格，但题目额外保证最多 25 个格子有黄金。这个数字才是真正的规模上界——路径只能在非零格子里走，所以搜索树的深度不超过 25，且这 25 个格子未必连通。这条约束是明确的「放心暴搜」信号：如果没有它，$3^{225}$ 是不可想象的。

还要注意「起点任意」。最优路径的起点无法预判，因此必须枚举每个非零格子各搜一次，不能只从某个特定位置开始。

边界上：所有格子都是 0 时答案为 0；单个孤立的非零格子，答案就是它自己；路径长度为 1 也是合法路径，不需要「至少走两步」。

解法：原地标记回溯

核心思路

从暴力的角度想：枚举所有不自交的路径并求和取最大。路径数量是指数级的，但正如上面分析的，非零格子最多 25 个，指数的底数也只有 3（进入一个格子后，四个方向里有一个是来路），所以直接搜是可以接受的——问题只在于怎么把「不自交」这个约束高效地表达出来。

朴素的表达方式是给每条路径带一个访问集合，进入递归时复制一份。瓶颈立刻出现：每层复制一个 $O(mn)$ 的布尔矩阵，指数条路径乘以线性复制，代价和内存都不可接受。

关键观察有两点。第一，路径的自交约束具有「进入时生效、退出时失效」的栈式结构：一个格子只在「当前递归调用链上」才算被占用，一旦回溯出去，它对其他分支就完全自由了。这正是回溯法「修改现场 + 恢复现场」的适用场景，不需要为每条路径各存一份状态，全局共用一份即可。第二，题目已经给了一个现成的标记位：值为 0 的格子本来就不可进入，所以把当前格子临时置为 0，语义上就等同于「此格已被占用」，连额外的 visited 数组都省了。

递归函数的语义定义为：dfs(row, col) 返回「在当前占用集合的前提下，从 (row, col) 出发（包含该格自身）还能收集到的黄金最大值」。它满足递推关系——答案等于本格黄金数，加上四个方向中「可进入的邻居各自 dfs 结果」的最大值；若四个方向都不可进入，加数为 0，这也自然覆盖了「随时可以停下」的规则（停下永远是候选之一，而黄金非负所以多走不会变差，取 max(0, ...) 的写法把两种情况统一了）。

回溯不变量：每次 dfs(row, col) 调用返回之后，grid 必须与调用之前逐格相同。维持这条不变量的代价是固定的两句——进入时 gold = grid[row][col]; grid[row][col] = 0;，返回前 grid[row][col] = gold;。有了它，兄弟分支之间、不同起点之间才互不干扰，外层的双重循环枚举起点才是正确的。

最后，这里不能加记忆化。dfs(row, col) 的结果依赖于当前已被占用的格子集合，同一个 (row, col) 在不同路径下答案不同，缓存会直接算错——这也是本题和 329「矩阵中的最长递增路径」的分水岭：后者的严格递增天然保证不会走回头路，状态只与坐标有关，才能记忆化。

解题步骤

外层双重循环枚举起点，只对 grid[row][col] > 0 的格子发起搜索。为什么要枚举全部：最优路径的起点未知，且非零格子可能分成互不连通的几块，只从一处出发会漏掉其他连通块。为什么跳过 0：从 0 出发的路径第一步就非法，dfs 会返回 0，白跑一趟。

进入 dfs 后先把本格黄金存进局部变量 gold，再把格子置 0。为什么必须先存：置 0 之后原值就永久丢失了，返回时既算不出总和也恢复不了现场。这两句的先后顺序是本题唯一一处不可交换的操作。

枚举四个方向，用统一的方向数组而不是四段复制粘贴。为什么：四段重复代码是白板上最容易写错下标的地方（复制后忘改符号），方向数组把「上下左右」压成一次循环，出错面小得多。

合法性判断三合一：行列在界内、且目标格 > 0。为什么把「大于 0」也算进合法性：值为 0 既可能是原本就没金子，也可能是被当前路径占用的标记，两种情况都不允许进入，语义正好统一，无需区分。

取四个方向返回值的最大值 bestNext，初值设为 0。为什么初值是 0 而不是负无穷：走不动时应当停下、只拿本格的金子，bestNext = 0 正好表达「不再往下走」这个合法选择。

返回前恢复 grid[row][col] = gold，再返回 gold + bestNext。为什么恢复必须在返回前而不是由调用方负责：让每个 dfs 自己保证「进出网格状态一致」，调用方就不必关心细节，这是回溯代码可靠的关键——谁修改谁恢复。

用每个起点的返回值更新全局答案，ans 初值为 0，覆盖了全网格无黄金的情形。

以 grid = [[0,6,0],[5,8,7],[0,9,0]] 走一遍（答案是 24）。

起点枚举到 (0,1)（值 6）时：置 0，网格中间列变成 [0,8,9] 这一竖。四个方向里只有 (1,1) 值 8 可进入。

进入 (1,1)：存下 8 并置 0。此时它的四邻是 (0,1) = 0（被占用，挡住了回头路）、(2,1) = 9、(1,0) = 5、(1,2) = 7。

分支 (2,1) = 9：置 0 后四邻全是 0，返回 9；返回前恢复成 9。

分支 (1,0) = 5：置 0 后四邻全是 0（(1,1) 正被占用），返回 5；恢复。

分支 (1,2) = 7：同理返回 7；恢复。

回到 (1,1)：bestNext = max(9, 5, 7) = 9，返回 8 + 9 = 17，恢复 (1,1) = 8。

回到 (0,1)：返回 6 + 17 = 23，恢复 (0,1) = 6。ans = 23。

起点枚举到 (2,1)（值 9）时同理走出 9 → 8 → 6，得 9 + 8 + 6 = 23；而起点 (1,0) = 5 走出 5 → 8 → 9 得 22。

真正的最优出现在起点 (0,1) 的另一种走法之外——注意到 6 → 8 → 9 是 23，而 7 → 8 → 9 是 24：起点枚举到 (1,2) = 7 时，进入 (1,1) = 8，此时 (1,2) 已被占用，剩下三个邻居中 9 最大，返回 7 + 8 + 9 = 24。ans 更新为 24。

全部起点枚举完毕，返回 24。可以看到，若某一层忘了恢复现场，后面这些起点看到的网格就已经残缺不全，24 这条路径根本走不出来。

代码实现

class Solution {
    private static final int[][] DIRECTIONS = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };

    public int getMaximumGold(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int ans = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] > 0) {
                    ans = Math.max(ans, dfs(grid, row, col));
                }
            }
        }

        return ans;
    }

    private int dfs(int[][] grid, int row, int col) {
        int gold = grid[row][col];
        grid[row][col] = 0;

        int bestNext = 0;
        for (int[] direction : DIRECTIONS) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];
            if (isValid(grid, nextRow, nextCol)) {
                bestNext = Math.max(bestNext, dfs(grid, nextRow, nextCol));
            }
        }

        // 恢复现场，保证其他搜索分支仍然可以经过这个格子。
        grid[row][col] = gold;
        return gold + bestNext;
    }

    private boolean isValid(int[][] grid, int row, int col) {
        return row >= 0
            && row < grid.length
            && col >= 0
            && col < grid[0].length
            && grid[row][col] > 0;
    }
}

func getMaximumGold(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])
    directions := [][2]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }

    var dfs func(row int, col int) int
    dfs = func(row int, col int) int {
        gold := grid[row][col]
        grid[row][col] = 0

        bestNext := 0
        for _, direction := range directions {
            nextRow := row + direction[0]
            nextCol := col + direction[1]
            if nextRow >= 0 && nextRow < rows &&
                nextCol >= 0 && nextCol < cols &&
                grid[nextRow][nextCol] > 0 {
                nextGold := dfs(nextRow, nextCol)
                if nextGold > bestNext {
                    bestNext = nextGold
                }
            }
        }

        // 恢复现场，保证其他搜索分支仍然可以经过这个格子。
        grid[row][col] = gold
        return gold + bestNext
    }

    ans := 0
    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] > 0 {
                gold := dfs(row, col)
                if gold > ans {
                    ans = gold
                }
            }
        }
    }

    return ans
}

复杂度分析

时间复杂度：$O(g \cdot 3^g)$，其中 g 是有黄金的格子数，题目保证 $g \le 25$。凭什么：外层枚举 g 个起点各搜一次；每次搜索中，路径的第一步有 4 个方向可选，之后每一步因为来路已被置 0 而最多只剩 3 个方向，路径长度上界是 g，故单次搜索的分支数是 $O(3^g)$，每个节点内部只做常数次操作。实际远达不到这个上界——只有当 25 个格子紧密连通时才接近最坏，稀疏分布时搜索空间会小得多。

空间复杂度：$O(g)$。凭什么：原地标记省掉了 visited 数组，唯一的额外开销是递归调用栈，而栈深度等于当前路径长度，不超过非零格子数 g。方向数组是固定大小的常量。

关键点总结

判断该用 DP 还是回溯，看子问题是否只依赖少量状态：本题的可行走法依赖整条已走路径，状态无法压缩，因此只能搜索。这个判据可以直接迁移到所有「路径不能自交」的题目。

回溯的核心纪律是「谁修改，谁恢复」：在函数内部完成置位与还原，让每次调用对外表现为无副作用，调用方才敢放心地在循环里连着调。这条纪律比记住「回溯要撤销」更可操作。

复用题目已有的非法值当访问标记是省空间的常用技巧：本题 0 本来就不可进入，置 0 与「已占用」语义天然一致，省下一个 $O(mn)$ 的 visited。面试时点出这一步能体现对题意的精读。

约束就是解法的说明书：题面特意写「最多 25 个格子有黄金」，就是在告诉你指数级搜索是被允许的。看到小得反常的规模上界，先想暴搜与状压，而不是硬凑多项式解法。

本题不能记忆化，因为返回值依赖当前占用集合而非仅仅坐标。面试官很可能追问「能不能加缓存加速」，答「不能，并说出反例结构」是加分点；对照 329 题的严格递增条件说明何时才可以缓存，效果更好。

起点不确定时就枚举全部起点，别试图用「从最大值出发」之类的贪心剪枝——最优路径未必经过全局最大值所在的连通块。

易错点总结

忘记恢复 grid[row][col]：grid = [[0,6,0],[5,8,7],[0,9,0]] 从 (0,1) 搜完后中心的 8 与四周的值全被留成 0，后续起点 (1,2) = 7 只能孤零零地返回 7，最终输出 23 而正确答案是 24。

置 0 之前没有先保存原值：gold 读到的是已被清零的 0，返回值恒等于下游最大值，grid = [[1,2],[3,4]] 会算出 9 而不是 10，而且返回时把格子恢复成 0，网格被永久破坏。

额外开 visited 数组却忘了同步回溯：只把 visited[row][col] = true 写上、漏掉 = false，第一个起点搜完后整片区域被永久标记，后续起点全部返回 0。

只从第一个非零格子出发搜一次：grid = [[1,0,7],[0,0,0],[2,0,6]] 这类非零格子分成多个连通块的数据，只搜第一块会得到 1，而正确答案是 13。

允许走进值为 0 的格子「借道」：grid = [[1,0,7]] 若允许穿过中间的 0，会算出 8，但题目明确禁止进入空格子，正确答案是 7。

把 bestNext 初值设成负无穷或 Integer.MIN_VALUE：孤立格子 grid = [[5]] 四个方向都走不通，gold + bestNext 直接溢出成一个极小的负数，答案错得离谱；初值必须是 0，代表「就地停下」。

在 dfs 里给 (row, col) 加记忆化缓存：grid = [[1,2,3],[4,5,6],[7,8,9]] 中 (1,1) 的最优后续在「从上方来」和「从左方来」两种占用状态下完全不同，缓存第一次的结果会让后续路径重复计入已占用格子，答案偏大。

方向数组抄写时符号写错，例如把 {-1, 0} 误写成 {1, 0} 造成方向重复：grid = [[1,2],[3,4]] 会漏搜向上的分支，从 (1,0) 出发只能得到 3 + 4 = 7，错过 3 + 1 + 2 + 4 = 10。

越界检查写在数组访问之后：先取 grid[nextRow][nextCol] 再判断下标范围，nextRow = -1 时 Java 抛 ArrayIndexOutOfBoundsException、Go 直接 panic；条件必须按「先界内、后取值」的短路顺序书写。

误把「随时可以停下」理解成「必须走到无路可走」：这两者在本题恰好等价（黄金非负，多走不亏），但如果照着「必须走到底」去写，往往会额外加一个「四邻全不可走才更新答案」的判断，导致中途路径不被统计；换成含负值的变体题就会直接出错。

相似题目

题目	难度	考察点
79. 单词搜索	中等	同为网格回溯，但目标是匹配定串，可在字符不符时立刻剪枝
980. 不同路径 III	困难	要求走遍所有空格并到达终点，统计的是方案数而非最大权值
212. 单词搜索 II	困难	多词同时搜索，需用字典树把公共前缀合并，否则逐词回溯会超时
329. 矩阵中的最长递增路径	困难	严格递增天然无环，状态只与坐标有关，因此可以记忆化，正是本题的反例
695. 岛屿的最大面积	中等	求连通块大小，格子访问后无需恢复，是「不回溯」的对照写法
200. 岛屿数量	中等	只需统计连通块个数，可直接原地淹没，不涉及路径与权值
51. N 皇后	困难	同样是「修改现场 + 恢复现场」，但冲突判定靠列与对角线集合而非网格本身
698. 划分为k个相等的子集	中等	回溯 + 剪枝的经典，规模同样靠极小的 `n` 撑住，可对比两题的剪枝手法