# My DFS JAVA solution

• public class Solution {
public int minPathSum(int[][] grid) {
Map<Point, Integer> visited = new HashMap<Point, Integer>();
return findMin(grid, 0, 0, visited);
}

private int findMin(int[][] grid, int x, int y, Map<Point,Integer> visited){
Point p = new Point(x,y);
if (visited.containsKey(p)){
return visited.get(p);
}
int min = 0;
if (x == grid.length-1 && y == grid[0].length-1){
min = grid[x][y];
}
else if(x == grid.length-1){
min = grid[x][y]+findMin(grid, x, y+1, visited);
}
else if(y == grid[0].length-1){
min = grid[x][y]+findMin(grid, x+1, y, visited);
}
else{
min = grid[x][y] + Math.min(findMin(grid, x+1, y, visited), findMin(grid, x, y+1, visited));
}
visited.put(p, min);
return min;
}

private class Point {
private int x;
private int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
public boolean equals(Object o){
Point p = (Point)o;
if (x == p.x && y == p.y){
return true;
}
return false;
}
public int hashCode(){return x*100+y;}
}
}

• I replaced HashMap with Array to make it faster

public class Solution {
public int minPathSum(int[][] grid) {
int[][] visited = new int[grid.length][grid[0].length];
for (int i=0;i<visited.length;i++){
for (int j=0;j<visited[0].length;j++){
visited[i][j]=-1;
}
}
return findMin(grid, 0, 0, visited);
}
private int findMin(int[][] grid, int x, int y, int[][] visited){
if (visited[x][y]!=-1){
return visited[x][y];
}
int min = 0;
if (x == grid.length-1 && y == grid[0].length-1){
min = grid[x][y];
}
else if(x == grid.length-1){
min = grid[x][y]+findMin(grid, x, y+1, visited);
}
else if(y == grid[0].length-1){
min = grid[x][y]+findMin(grid, x+1, y, visited);
}
else{
min = grid[x][y] + Math.min(findMin(grid, x+1, y, visited), findMin(grid, x, y+1, visited));
}
visited[x][y]=min;
return min;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.