Follow up about LC problems minimum path sum


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 }