在矩阵回溯中进行累加和比较的注意点

1 总结

在回溯时，如果递归函数采用void返回，在入口处使用了sum变量，那么一般在初次调用dfs的地方，这个sum的初始值可能不是0,而是数组的对应指针的值，在比较操作的时候，需要在for循环开始之前进行，这样确保不遗漏corner case

2 题目

2.1 LC1219. 黄金矿工

2.1.1 答案：下面是我的答案，不能通过所有case

比如无法通过case, 正确答案是9,但是执行后的答案是7, [[0,6,1],[0,0,0],[0,9,0]]

从代码中我们可以看到比较值更新msum（msum=Math.max(msum,sum+grid[nx][ny]);）的时机不对，如果有一个非0值的周围都是0值，那么这个值本身没有参与比较，即潜在的最大值可能被忽略

class Solution {
	
    int msum=0;
    public int getMaximumGold(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        boolean vis[][]=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]!=0){
                    msum=0;
                    vis[i][j]=true;
                    dfs2(grid,i,j,vis,grid[i][j]);
                    vis[i][j]=false;

                    ans=Math.max(ans,msum);
                }
            }
        }
        return ans;
    }
    int[]dirs=new int[]{-1,0,1,0,-1};
    void dfs2(int[][] grid, int x, int y,boolean vis[][],int sum){
        for(int i=0;i<4;i++){
            int nx=x+dirs[i];
            int ny=y+dirs[i+1];
            if(nx>=0&&nx<grid.length&&ny>=0&&ny<grid[0].length){
                if(grid[nx][ny]==0)continue;
                if(vis[nx][ny])continue;
                vis[nx][ny]=true;
                msum=Math.max(msum,sum+grid[nx][ny]);
                dfs2(grid,nx,ny,vis,sum+grid[nx][ny]);
                vis[nx][ny]=false;

            }
        }
    }
}

2.1.2 标准答案：（相比于2.1.1答案，仅仅是移动了一行代码就通过了所有case）

class Solution {
    int msum=0;
    public int getMaximumGold(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        boolean vis[][]=new boolean[m][n];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]!=0){
                    msum=0;
                    vis[i][j]=true;
                    dfs2(grid,i,j,vis,grid[i][j]);
                    vis[i][j]=false;

                    ans=Math.max(ans,msum);
                }
            }
        }
        return ans;
    }
    int[]dirs=new int[]{-1,0,1,0,-1};
    void dfs2(int[][] grid, int x, int y,boolean vis[][],int sum){
    	msum=Math.max(msum,sum);// 移动的那行代码
        for(int i=0;i<4;i++){
            int nx=x+dirs[i];
            int ny=y+dirs[i+1];
            if(nx>=0&&nx<grid.length&&ny>=0&&ny<grid[0].length){
                if(grid[nx][ny]==0)continue;
                if(vis[nx][ny])continue;
                vis[nx][ny]=true;
                dfs2(grid,nx,ny,vis,sum+grid[nx][ny]);
                vis[nx][ny]=false;

            }
        }
    }
}

2.1.3 官方标准答案：下面是标准答案，通过所有case

class Solution {
    int[][] g;
    boolean[][] vis;
    int m, n;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public int getMaximumGold(int[][] grid) {
        g = grid;
        m = g.length; n = g[0].length;
        vis = new boolean[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != 0) {
                    vis[i][j] = true;
                    ans = Math.max(ans, dfs(i, j));
                    vis[i][j] = false;
                }
            }
        }
        return ans;
    }
    int dfs(int x, int y) {
        int ans = g[x][y];
        for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (g[nx][ny] == 0) continue;
            if (vis[nx][ny]) continue;
            vis[nx][ny] = true;
            ans = Math.max(ans, g[x][y] + dfs(nx, ny));
            vis[nx][ny] = false;
        }
        return ans;
    }
}

作者：宫水三叶
链接：https://leetcode.cn/problems/path-with-maximum-gold/solutions/1245984/gong-shui-san-xie-hui-su-suan-fa-yun-yon-scxo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.1.4 总结：