# Easy to understand O(mn) time and O(1) space DP solution in Java with explanation

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

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