
The formula : C(n + m  2, n  1)
Overflow is the problem. Would you do it with this formula? Thanks. 
Using DP Time Complexity is O(m * n) Space Complexity is O(min(m, n))
class Solution { public: int uniquePaths(int m, int n) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if((m <= 0)  (n <= 0)) return 0; if((1 == m)  (1 == n)) return 1; int map[n + 1]; memset(map, 0, sizeof(map)); for(int i = 1; i <= n; i ++) map[i] = 1; for(int i = 2; i <= m; i ++) { for(int j = 2; j <= n; j ++) { map[j] += map[j  1]; } } return map[n]; } };
Solve Unique Paths with linear algorithm?


I have no idea what the formula means. I think you can use some math formula to solve this problem.
Here is my solution.class Solution { public: int uniquePaths(int m, int n) { vector<int> map(m+1, 0); map[1]=1; for(int i=0; i<n; i++){ for(int j=1; j<=m; j++) map[j] = map[j1]+map[j]; } return map[m]; } }
;

Here is the implementation of C(m,n) without overflowing the answer.
int gcd(int a, int b) { while(b) { int c = a%b; a = b; b = c; } return a; } int C(int m, int n) { if(m  n < n) { n = m  n; } int result = 1; for(int i = 1; i <= n; i++) { int mult = m; int divi = i; int g = gcd(mult,divi); mult /= g; divi /= g; result /= divi; result *= mult; m; } return result; }

Divide as you go along to delay overflow
public class Solution { public int uniquePaths(int m, int n) { return combination(m + n  2, n  1); } private int combination(int m, int n){ if(n > m / 2) return combination(m, m  n); else{ double result = 1; for(int i = 1; i <= n; i++){ result *= m  n + i; result /= i; } return (int)result; } } }

You perform one passage more with a map n + 1 because you fill your map with 1 0 0 0 ... at the beginning.
You can cut first step by filling it with 1 1 1 1 1.{
int uniquePaths(int m, int n) {// Reduces the problem to m <= n, because internal loop is faster. if (m > n) swap(m, n); if (m <= 1) return m; // Corner cases, one border is 0 or 1. // Uses a map to memoize previous results: vector<int> map(n, 1); // The map is filled of 1, so that first step is already done. // For every horizontal step... for (int i = 1; i < m; ++i) { // For every vertical step... for (int j = 1; j < n; ++j) { map[j] += map[j  1]; } } // The last element contains our solution. return map[n  1]; }
}
}