Solve Unique Paths with linear algorithm?

Question

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

Answer 1

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

Comments

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.

Answer 2

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

;

Comments

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)

Answer 3

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

}