# C++, dp, O(n^2) time, O(n) space

• 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];
}``````

• Quite neat solution. Could you explain the logic behind this solution? Thanks in advance.

• This post is deleted!

• @whitehat Format is not so good, i hope it can help you.

• @John1993: I have formatted your post, hope this helps.

• It always goes wrong when edit my answer, thank you so much!

• Thank you for the explanation

• Good idea to optimize the space complexity.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.