Concise Java bottom-up solution


  • 0
    Y

    Instead of using top-down approach, I use bottom-up.

    Start from the bottom-right point, every time we go either up or left to reach the top-left point. This means to reach point (r, c), we can either walk from (r + 1, c) or (r, c + 1).

    When the path out of the boundary, we give it the maximum integer value. Therefore, we can make sure the other path (which is not out of the boundary) will be chosen.

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] path = new int[m][n];
        path[m - 1][n - 1] = grid[m - 1][n - 1];
    
        for(int r = m - 1; r >= 0; r--) {
            for(int c = n - 1; c >= 0; c--) {
                if(r + 1 == m && c + 1 == n) continue;
                int up = (r + 1 == m)? Integer.MAX_VALUE : path[r + 1][c];
                int left = (c + 1 == n)? Integer.MAX_VALUE : path[r][c + 1];
                path[r][c] = grid[r][c] + Math.min(up, left); 
            }
        }
    
        return path[0][0];
    }

Log in to reply
 

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