Skip to content

Latest commit

 

History

History
 
 

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

README.md

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