Java Clear Easy to Understand Version using DP


  • 0
    W
    public int minPathSum(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        // initial first column
        for(int i = 1;i<m;i++){
            grid[i][0] +=grid[i-1][0];
        }
        
        // initial first row
        for(int j = 1;j<n;j++){
            grid[0][j]+=grid[0][j-1];
        }
        
        // update the rest
        for(int i = 1 ; i < m;i++){
            for(int j = 1; j < n;j++){
                grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }

Log in to reply
 

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