Concise java solution O(n) space


  • 2
    J
    public int minPathSum(int[][] grid) {
        int[] d=new int[grid.length];
        d[0]=grid[0][0];
        for(int i=1;i<grid.length;i++)
            d[i]=d[i-1]+grid[i][0];
        for(int j=1;j<grid[0].length;j++){
            d[0]+=grid[0][j];
            for(int i=1;i<grid.length;i++){
                d[i]=Math.min(d[i-1],d[i])+grid[i][j];
            }
        }
        return d[grid.length-1];
    }

Log in to reply
 

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