The idea is like this:

Since we only need to know `N[m-1][n-1]`

for a m*n grid, it is a waste of space to keep the whole 2-dimensional array. And we also know that `N[i][j] = N[i-1][j] + N[i][j-1]`

, so if we use only a one dimensional array and let `N[i] = N[i] + N[i-1]`

. i.e. the `N[i]`

at the left side of the equation and `N[i-1]`

actually stores the number of path at the next row in a 2-dimensional array, and `N[i]`

at the right side of the equation stores the number of paths at the current row in a 2-dimensional array. So in general, every element on the left side of `N[i]`

in the 1 dimensional array is actually the value at the next row if in a 2-dimensional array.

By filling the array from left to right, we will never rewrite a value before we making use of it.

```
public class Solution {
public int uniquePaths(int m, int n) {
/*
Dynamic Programming
Bottom-up approach
If we use Num[n] to denote the number of paths and we fill this form from left to right, we will never rewrite a value before we make use of it.
O(mn) time and O(n) space
*/
if (m == 0 || n == 0){
return 0;
}
int[] Num = new int[n];
for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j++){
if (i == 0 || j == 0){
Num[j] = 1;
}
else {
Num[j] += Num[j-1];
}
}
}
return Num[n-1];
}
```

}