My DFS JAVA solution


  • 0
    Q
    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;}
        }
    }

  • 0
    Q

    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; 
        }
    }

Log in to reply
 

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