北京微信网站建设电话咨询企业网络规划设计方案
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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。