There are (m+n-2) steps in each path, (m-1) of them are downwards and (n-1) are rightwards.

Thus the answer is the combination C(m+n-2)(m-1), or C(m+n-2)(n-1).

Use long int to avoid overflow.

```
class Solution {
public:
int uniquePaths(int m, int n) {
long cnt=1;
if (m>n) swap(m,n);//to have a shorter 'for' loop
n--;
for (int i=1;i<m;i++) cnt=cnt*(n+i)/i;
return cnt;
}
};
```