Follow up about LC problems minimum path sum


  • 0
    Z

    Can you print out the path? Here is the original problem link


  • 0

    dynamic programming, I think


  • 1
    D

    This is an easy one. For every cell in the grid, just keep a pointer to its predecessor. After the entire grid has been traversed, traverse the predecessors backwards and you should have the path.

    List<String> getShortestPath(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n];
            int[][] dir = new int[m][n];
    
            for (int i = 0; i < m; i++) {
                Arrays.fill(dir[i], -1);
            }
            int[][] dp = new int[m][n];
            // Each element in this array would be in {L, N, U} indicating left, no movement, up respectively.
            char[][] dir = new char[m][n];
            dp[0][0] = grid[0][0];
            int i,j;
            for (i = 1; i < m; i++) {
                dp[i][0] = dp[i - 1][0] + grid[i][0];
                Arrays.fill(dir[i], 'N');
            }
            for (j = 1; j < n; j++) {
                dp[0][j] = dp[0][j - 1] + grid[0][j];
            }
            
            for (i = 1; i < m; i++) {
                for (j = 1; j < n; j++) {
                    if (dp[i - 1][j] < dp[i][j - 1]) {
                        dp[i][j] = dp[i - 1][j] + grid[i][j];
                        dir[i][j] = 'L';
                    } else {
                        dp[i][j] = dp[i][j - 1] + grid[i][j];
                        dir[i][j] = 'R';
                    }
                }
            }
            List<String> path = new ArrayList<String>();
            int x = m - 1;
            int y = n - 1;
            while (dir[x][y] != 'N') {
                path.add(0, x + "," + y);
                if (dir[x][y] == 'U') {
                    x--;
                } else {
                    y--;
                }
            }
            path.add(x + "," + y);
            return path
    }
    

Log in to reply
 

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