This technique uses a recursive algorithm, much like the one used to find a path between 2 points in a two dimensional array.

Basically, you recursively select the path that has the shorter sum at each step (which is stored in `right`

and `down`

). The first base case just returns the value in the bottom right spot when we reach there. The second base case will return `Integer.MAX_VALUE`

when we go out of the grid so that we do not select this invalid path.

**Dynamic Programming**

Well, the above algorithm works, but without DP it's really slow. If you recursively think about it and imagine that you are at some spot `(i, j)`

in the grid, you have already computed the path with the shortest sum till there. Instead of using another two dimensional array, I multiply the value in the original grid at `(i, j)`

with `-1`

. While recursively traversing, if I come across a value that is negative, I know that I have already computed the shortest path to this spot, which is simply `-1 * value_at_spot`

** Code **

```
public int minPathSum(int[][] grid) {
return solve(grid, 0, 0);
}
private int solve(int[][] grid, int i, int j) {
if (i == grid.length-1 && j == grid[0].length-1)
// base case 1
return grid[i][j];
if (i == grid.length || j == grid[0].length) {
// base case 2 (invalid spot)
return Integer.MAX_VALUE;
}
if (grid[i][j] < 0)
return -1*grid[i][j]; // DP - already have lowest sum path
int right = solve(grid, i, j+1);
int down = solve(grid, i+1, j);
if (right < down) {
grid[i][j] = -1* (grid[i][j] + right);
}
else {
grid[i][j] = -1* (grid[i][j] + down);
}
return -1 * grid[i][j];
}
```