Guessing

1 * 1 matrix have 1 unique path

+---+
| 1 |
+---+

1 * 2 matrix have 1 unique path

+---+---+
| 1 | 1 |
+---+---+

1 * n or n * 1 matrix have 1 unique path

+---+---+---------
| 1 | 1 |   -->
+---+---+---------

2 * 2 matrix have 2 unique paths

+---+---+
| 1 | 1 |
+---+---+
| 1 | 2 |
+---+---+

+-----+
|     |
|     v
+--->

a grid can only be entered from the grid on its top or left.

Grid x

+---+---+---+---+---+---+---+
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 1 | 2 |   |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   |   |   | m |   |   |
+---+---+---+---+---+---+---+
| 1 |   |   | n | x |   |   |
+---+---+---+---+---+---+---+
| 1 |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   |   |   |   |   |   |
+---+---+---+---+---+---+---+

Assume that

  • from top-left to grid m, there are m unique paths
  • from top-left to grid n, there are n unique paths

So that

  • there is m unique paths from top-left to grid x via grid m
  • there is n unique paths from top-left to grid x via grid n

  • there is m + n unique paths from top-left to grid x via grid m and grid n

Fill up the matrix

we can build a matrix that

  • all [0][?] = 1
  • all [?][0] = 1

fill up grids in the matrix one by one [x][y] = [x - 1][y] + [x][y - 1]

the value in the bottom-right grid is how many paths from top-left to bottom-right.