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 sums
- 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.
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
| | | | m | | | |
+---+---+---+---+---+---+---+
| | | n | x | | | |
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
Assume that
grid mhas a minimum path summgrid nhas a minimum path sumn
So
the minimum path sum grid x is MIN(m, n) + x
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