# Solve Unique Paths with linear algorithm?

1. The formula : C(n + m - 2, n - 1)
Overflow is the problem. Would you do it with this formula? Thanks.

2. 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];
}
};``````

• This post is deleted!

• 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[j-1]+map[j];
}
return map[m];
}
}
``````

;

• This post is deleted!

• 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;
}
``````

• assume it is a area of n*m, width is n
n+m-2 means the length of one path
n-1 means you have to choose (n-1) times to move horizontally
Hence the total possible path number is Combination(n+m-2, n-1)

• m=3, n = 4 will not return correct answer

• That is because `m` should not be smaller than `n`

• I see :-)
"C" is short for "Combination" not the original function uniquePaths(m, n)
Elegant gcd !!!

• Yep. `C(m, n)` will return the number of different ways you can choose n items out of m.

• 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;
}
}

}``````

• This post is deleted!

• Your solution worked:), nice use of setting the result be double type.

• actually you can just set result as long

• 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];
}
``````

}
}

• C(198, 99) = -2138017796
It is still overflow

• Then use long long

• result /= divi; // how to prove result can be divided by divi?
result *= mult;

• Otherwise result will not be an integer.

• Hi porker2008,

For example.
s1 = m * (m - 1) * (m - 2) * .... * (m - n + 1)
s2 = 1 * 2 * 3 * 4 * .... n

we can prove b = 1 * 2 * 3 * 4 can be divided by m * (m -1) * (m - 2) * (m - 3).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.