Use the given 2D array and update grid[i][j] to store the minimum path until [i][j].

First update the upper most row as the dynamic programming algorithm's initial value.

Do the same to the left most column.

Then update grid[i][j] with the minimum path reaching to, from i = 1, j = 1 from left to right (i++), up to down(j++).

Then we will get the result at bottom right.

The time complexity is O(mn) since we have a two levels loop

The space complexity is O(1)

public class Solution {

public int minPathSum(int[][] grid) {

// redefine grid[i][j] to the minimum path reaching grid[i][j]

for (int i = 1; i < grid.length; ++i) {

grid[i][0] += grid[i - 1][0];

}

for (int j = 1; j < grid[0].length; ++j) {

grid[0][j] += grid[0][j - 1];

}

for (int i = 1; i < grid.length; ++i) {

for (int j = 1; j < grid[0].length; ++j) {

grid[i][j] += Math.min(grid[i -1][j], grid[i][j -1]);

}

}

return grid[grid.length - 1][grid[0].length - 1];

}

}