迷宫寻宝：贪心算法是否最优？

在 n 行 m 列的迷宫中，探险者从左上角 (0, 0) 出发，只能向右或向下移动，最终到达右下角 (n, m)。每个节点都包含不同数量的金币，探险者希望在出发前计算出能获得的最大金币数量。

贪心算法思路：

探险者首先想到的是递归地遍历所有路径，找到获得金币最多的路径。然而，这种方法在迷宫规模较大时效率低下。因此，探险者尝试使用贪心算法：每次都选择剩余可到达节点中金币最多的节点。

贪心算法是否正确？

遗憾的是，贪心算法并不总是能找到最优解。虽然选择当前步数中金币最多的节点能让当前获得最多金币，但无法保证最终获得的总金币数最大。

反例：

考虑以下迷宫数据：

[0, 2, 0]
[1, 4, 0]
[0, 0, 0]

按照贪心算法，我们会选择初始位置右边的节点 (0, 1)，因为它有 2 个金币。然后选择下方的节点 (1, 1)，因为它有 4 个金币。最终到达终点，获得 6 个金币。

然而，如果选择初始位置下方的节点 (1, 0)，然后选择右边的节点 (1, 1)，最终到达终点，我们将获得 8 个金币。

结论：

贪心算法在迷宫寻宝问题中并不一定能找到最优解。它可能导致获得的金币数量不是最大化的。为了找到最优解，需要考虑更复杂的算法，例如动态规划。