Simple and straightforward method


  • 0
    M

    Dynamic programming in 2-D matrix
    Time and space complexity: O(m*n)

    public int minPathSum(int[][] grid) {
            int row = grid.length, col = grid[0].length;
            if(grid == null || grid.length == 0 || row == 0 || col == 0)
                return 0;
            int[][] res = new int[row][col];
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    if(i == 0 && j == 0)
                        res[i][j] = grid[i][j];
                    else if(i != 0 && j == 0)
                        res[i][j] = res[i-1][j] + grid[i][j];
                    else if(i == 0 && j != 0)
                        res[i][j] = res[i][j-1] + grid[i][j];
                    else
                        res[i][j] = Math.min(res[i-1][j] + grid[i][j], res[i][j-1] + grid[i][j]);
                }// for ends
            }// for ends
    
            return res[row-1][col-1];
        }
    

Log in to reply
 

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