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.

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