Day 16, 62 Unique Path

Unique Path
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
-------------
-- REFERENCE click me --
Solution #1 straight forward. each step has two ways until passes borders or hit the finish

class Solution {
public:

    int backtrack (int x, int y, int m, int n) {
        if (x == m && y == n) {
            return 1;
        }
        if (x>m || y>n) {
            return 0;
        }
        return backtrack(x+1,y,m,n) + backtrack(x,y+1,m,n);
    }

    int uniquePaths(int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return backtrack(1,1,m,n);
    }
};

Solution #1 DP, memoization

class Solution {
public:
    int backtrack (int x, int y, int m, int n,int ma[][102]) {
        if (x == m && y == n) {
            return 1;
        }
        if (x>m || y>n) {
            return 0;
        }
        
        if (ma[x+1][y] == -1) {
            ma[x+1][y] = backtrack(x+1,y,m,n,ma);
        }
        if(ma[x][y+1] == -1) {
            ma[x][y+1] = backtrack(x,y+1,m,n,ma);
        }
        return ma[x+1][y] + ma[x][y+1];
    }

    int uniquePaths(int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ma[102][102];
        for (int i=0;i<102;i++) {
            for (int j=0;j<102;j++) {
                ma[i][j] = -1;
            }
        }
        return backtrack(1,1,m,n,ma);
    }
};

Solution #3, DP bottom up

class Solution {
public:
    int uniquePaths(int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ma[102][102] = {0};
        ma[m+1][n] = 1; // set either [m][n+1] or [m+1][n] to 1
        for (int i=m;i>0;i--) {
            for (int j=n;j>0;j--) {
                ma[i][j] = ma[i+1][j] + ma[i][j+1];
            }
        }
        return ma[1][1];
    }
};

O(n) space

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n,0);
        dp[n - 1] = 1;
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[j] = dp[j] + dp[j + 1];
            }
        }
        return dp[0];
    }
};

Solution #4 combinatorics
C(m+n-2, n-1)
OJ会overflow

class Solution {
public:
    int comb(int n) {
        int rt = 1;
        for (int i = 1; i <= n; i++) {
            rt *= i;
        }
        return rt;
    }

    int uniquePaths(int m, int n) {
        return comb(m + n - 2) / comb(n - 1) / comb(m - 1);
    }
};