The state transition equation is: `memo[i][j] = memo[i][j-1] + memo[i-1][j]`

For example: A 3x4 grid, you need to reach bottom-right corner from top-left corner.

We use memo[3][4] to save number of paths.

```
x x x x
x x x x
x x x x
```

Number of paths of first row is 1 1 1 1, because you can only go down and left, you only have one way to go to destination in row 0. So I init the row 0 with 1.

And the second row, we only have one way to go to grid[1][0], is start->down->down.so memo[1][0] = 1.

And for memo[1][1], you can go from grid[1][0] and grid[0][1], so memo[1][1] = memo[1][0]+memo[0][1], and the others are the similar.

so the number of paths of 3x4 grid is:

```
1 1 1 1
1 2 3 4
1 3 6 10, and return memo[2][3].
```

And take a closer look at the question, you can just use O(n) space, because when you calculate m[i][j], you need to add up m[i][j-1] and m[i-1][j].

In my solution, m[i][j-1] is m[i-1],has been calculated just before m[i]j, and m[i-1][j] is old m[i] saved in m[i].

You add up old m[i] and new m[i-1], the answer saves in m[i].

My English is not so good, I hope this can answer you question.

```
int uniquePaths(int m, int n) {
int *memo = new int[n];
for(int i = 0; i < n; i++)
memo[i] = 1;
for(int i = 1 ; i < m; i++)
for(int j = 1; j < n; j++)
memo[j] += memo[j-1];
return memo[n-1];
}
```