```
/**
* Time complexity: O(m*n)
* Space complexity: O(m+n)
*
* This method is an optimized version of simple dynamic programing solution from space O(m*n) to O(m+n).
*
* By observing the order of calculation in simple dynamic programming:
*
* for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
...
}
}
* We can find that every row is used exactly once, and in order.
* Therefore allocating a row of memorizing array is enough.
*/
int uniquePaths(int m, int n) {
// ensure m > n to save space since we are going to allocate an array of size n.
if(n < m) return uniquePaths(n, m);
vector<int> dp(n, 1);
for(int i = 1; i < m; ++i) {
for(int j = 1; j < n; ++j) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
```