- Recursive[Time Limit Exceeded]

```
public int walk(int i, int j, int m, int n){
if(i == m && j == n)
return 1;
if(i > m || j > n)
return 0;
return walk(i + 1, j, m, n) + walk(i, j + 1, m, n);
}
public int uniquePaths(int m, int n) {
return walk(1, 1, m, n);
}
```

- Dynamic Programming.

Let `paths[i][j]`

be the unique ways to position(i, j).

`paths[i][j] = paths[i-1][j] + paths[i][j-1]`

.

Because `paths[i][j]`

depends only on the left state and the up state, we minus space complexity from O(mn) to O(n).

**Complexity: Time O(mn), Space O(n).**

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