# Unique Paths

## 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.

### Source code *Read on Github*

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