Unique_Paths

/*
Unique Paths 
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?
Note: m and n will be at most 100.
*/
//version1
class Solution {
public:
	int uniquePaths(int m, int n) {
    int numpaths[m][n];
    for (int i=0; i<m; ++i)
        numpaths[i][0]=1;
    for (int j=0; j<n; ++j)
        numpaths[0][j]=1;
    for (int i=1; i<m; ++i)
        for (int j=1; j<n; ++j)
            numpaths[i][j]=numpaths[i-1][j]+numpaths[i][j-1];
    return numpaths[m-1][n-1];
}
};

1.REMARK: I wrote version2 and version3 at first. They work only if m and n are small. Did not write version1 myself. Version1 uses extra space increase the speed. Also, it does not use recursion.  
IDEA: Use a m*n 2dimensional array numpaths[][] to store the number of unique paths. numpaths[i][j] means the number of unique paths from the top-left corner to the position at [i][j]. Note the equation: numpaths[i][j] = numpaths[i-1][j] + numpaths[i][j-1].
2.Time: O(m+n)

//version2:Too slow when m and n are large.
int uniquePaths(int m, int n) {
    if (m==1 && n==1) return 1;
    else if (m==1) return 1;
    else if (n==1) return 1;
    else return (uniquePaths(m-1,n)+uniquePaths(m,n-1));
}


//version3:Too slow when m and n are large.
class Solution {
public:
    
    int factorial(int n)
{
    if (n==0) return 1;
    int result=1;
    for (int i=1; i<=n; ++i)
	    result *= i;
    return result;
}

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