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

• dynamic programming, I think

• 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--;
}
}