# Minimum Path Sum

## Picking up numbers on Unique Paths

From top left to the right bottom there is `n`

Unique Paths.

Picking up the numbers alone each path and sum them, we can collect all `Path Sum`

.

e.g. a matrix with numbers

```
+---+---+
| 1 | 3 |
+---+---+
| 2 | x |
+---+---+
```

`grid x`

has `2`

unique paths and `2`

`path sum`

s

- 1 + 3 + x
- 1 + 2 + x (minimum)

There are `2`

viable paths to `grid x`

, the grid on the left side of `grid x`

and the grid on top of `grid x`

.
We can choose the smaller path sum viable one, that will minimize path sum to `grid x`

.

## Grid x

```
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
| | | | m | | | |
+---+---+---+---+---+---+---+
| | | n | x | | | |
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
```

Assume that

`grid m`

has a minimum path sum`m`

`grid n`

has a minimum path sum`n`

So

the minimum path sum `grid x`

is MIN(m, n) + x

## Fill up the matrix

Generally, `P[x][y]`

is minimum path sum from top left.

`P[x][y] = MIN(P[x - 1][y], P[x][y - 1]) + grid[x][y]`

the overall answer is in the right bottom grid.

such filling up process is well know as Dynamic programming

### Source code *Read on Github*

```
1 public class Solution {
2 public int minPathSum(int[][] grid) {
3 // Note: The Solution object is instantiated only once and is reused by each test case.
4
5
6
7 int mx = grid.length;
8 if(mx == 0) return 0;
9
10 int my = grid[0].length;
11
12 for(int x = 1; x < mx ; x++){
13 grid[x][0] += grid[x - 1][0];
14 }
15
16 for(int y = 1; y < my ; y++){
17 grid[0][y] += grid[0][y - 1];
18 }
19
20 for(int x = 1; x < mx; x++){
21 for(int y = 1; y < my; y++){
22 grid[x][y] += Math.min(grid[x - 1][y], grid[x][y - 1]);
23 }
24 }
25
26 return grid[mx - 1][my - 1];
27 }
28 }
```