为什么只有回溯在这种情况下有效？

Question

我正在 LeetCode.com 上解决这个问题：

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty. Return the maximum amount of gold you can collect under the conditions:-
(a) Every time you are located in a cell you will collect all the gold in that cell;
(b) From your position you can walk one step to the left, right, up or down.
(c) You can't visit the same cell more than once;
(d) Never visit a cell with 0 gold.
(e) You can start and stop collecting gold from any position in the grid that has some gold.
For the grid: [[0,6,0],[5,8,7],[0,9,0]] the output is: 24.

我写了下面的代码：

class Solution {
public:
    int dig(vector<vector<int>>& grid, int i, int j) {
        if(i>=grid.size() || i<0 || j>=grid[0].size() || j<0 || grid[i][j]==0) return 0;
        
        //change begins...
        int gold=0;
        gold+=grid[i][j];
        grid[i][j]=0;
        gold+=max(dig(grid, i+1, j), max(dig(grid, i, j+1), max(dig(grid, i-1, j), dig(grid, i, j-1))));
        return gold;
        //change ends...
    }
    
    int getMaximumGold(vector<vector<int>>& grid) {
        vector<vector<int>> gridCopy=grid;
        
        int maxGold=0;
        for(int i=0; i<grid.size(); i++) {
            for(int j=0; j<grid[0].size(); j++) {
                if(grid[i][j]!=0) {
                    maxGold=max(maxGold, dig(gridCopy, i, j));
                    gridCopy=grid;
                }
            }
        }
        
        return maxGold;
    }
};

但是，它在输入时中断 [[1,0,7,0,0,0],[2,0,6,0,1,0],[3,5,6,7,4,2],[4,3,1,0,2,0],[3,0,5,0,20,0]]；产生 58 而不是 60.

我发现了另一个代码 here，它是相同的，除了上面的注释部分，它们有以下几行：

  g[i][j] = -g[i][j];
  auto res = max({ dfs(g, i + 1, j), dfs(g, i, j + 1), dfs(g, i - 1, j), dfs(g, i, j - 1) });
  g[i][j] = -g[i][j];
  return g[i][j] + res;

（当然，他们不会在嵌套的 for 循环中将 grid 分配给 gridCopy，因为他们将修改后的网格恢复为原始形式）。

我知道他们在回溯，而我没有。但是我无法理解我做错了什么，因为从逻辑上讲，我在做完全相同的事情。我使用调试语句来跟踪问题，但是由于有很多递归调用，因此很难跟进。

有人可以指出我上面的代码中的逻辑谬误是什么吗？

谢谢！

Answer 1

您所有的递归调用都可能会修改网格，并且不会恢复它。
这意味着第一次访问一个单元格将阻止所有其他后续尝试。

例如，如果首先计算 dig(grid, i+1, j)，则当您执行其他三个方向时，计算期间访问的单元格中有 none 可用。

如果您的代码恰好从左上角开始，在您的示例中先向下，您将访问 1-2-3-4-3 并卡住。
走完这条路，左上角就没有路了，虽然一开始有很多，而且有的比13多了很多。
（您可能认为您将从任一方向找到一条路径，但这取决于评估顺序。）

共享可变状态和递归是一个非常棘手的组合。

Answer 2

您的代码中有一点似乎有误：

//change begins...
        int gold=0;
        gold+=grid[i][j];
        grid[i][j]=0;
        gold+=max(dig(grid, i+1, j), max(dig(grid, i, j+1), max(dig(grid, i-1, j), dig(grid, i, j-1))));
        return gold;
        //change ends...

这里您更改了 grid[i][j] 的值，更改后的值正在影响您的输入，即您的输入集现在是错误的。由于 grid[i][j] 的值已更改，因此这将影响其余计算。

您可以做的是将 grid[i][j] 的初始值存储在该递归堆栈中的某处，并在您探索完该节点的所有路径后重新分配回 grid[i][j]。

例如：您的逻辑略有修改

//change begins...
        int gold=0;
        gold+=grid[i][j];
        int temp = grid[i][j];
        grid[i][j]=0;
        gold+=max(dig(grid, i+1, j), max(dig(grid, i, j+1), max(dig(grid, i-1, j), dig(grid, i, j-1))));
        grid[i][j] = temp;
        return gold;
        //change ends...

如果您在问题中使用那里的解决方案，您还可以节省在递归堆栈中创建内存的时间。

简单回答一下为什么只有回溯才能解决这个问题：

您需要了解您的解决方案，它看起来像：

查看每个网格项是否可以作为解决方案集的一部分。
为此，您 select 一个网格项目（项目值应大于 0）
然后你从那个项目探索周围的所有环境。并使用 DFS 继续探索他们的周围环境，等等，直到满足退出条件。
现在，在您的解决方案中，您已经改变了 grid[i][j] 的值（为了便于理解，假设 grid[2][3] 发生了改变）当且仅当项目 selected 存在于最终解决方案集中。
但是，在探索其他可能性的同时，如果您碰巧发现了一些存在更多金币的可能性。然后还有grid[2][3]会涉及到。您已将其标记为 0，即该节点的计算将出错。

因此，您需要恢复网格项的原始值grid[i][j]。你这样做的原因 0 是你不想再次包含它，因为你已经访问过。但是对于其他解决方案集，您需要原始值存在于那里。

为什么只有回溯在这种情况下有效？

Why does only backtracking work in this scenario?

c++

algorithm

backtracking

depth-first-search