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?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

There are several approaches to this problem.

1. Recursion:
The code is the simplest but quite slow.

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m<1||n<1) return 0;
        if (m==1&&n==1) return 1;
       
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }
};

2. Math:
In total the robot should walk m + n - 2 steps, m - 1 steps to right and n - 1 steps to bottom,  so we need to select which m - 1 steps to be right, or which n-1 steps to bottom. The problem is actually a combination problem. We just need to calculate (n + m - 2)! / ((m - 1)! * (n - 1)!).

The tricky part to code is to avoid overflow when m and n are big.
a. Calculate (n+m-2)*(n+m-2-1)*(n+m-2-2)*..*max(m,n)
b. Use type long long instead of int when calculating the factorial

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m<1||n<1) return 0;
        if (m==1&&n==1) return 1;
       
        int max = std::max(m,n)-1;
        int min = std::min(m,n)-1;
       
        int r = int(factorial(max+min,max+1)/(factorial(min,1)));
        return r;
    }
   
    long long factorial(int x,int start)
    {
        long long r=1;
        for (int i=x;i>=start; i--)
        {
            r=r*i;
        }
        return r;
    }
};

A more concise implementation:
class Solution {
    public:
        int uniquePaths(int m, int n) {
            int N = n + m - 2;// how much steps we need to do
            int k = m - 1; // number of steps that need to go down
            double res = 1;
            // here we calculate the total possible path number
            // Combination(N, k) = Combination(N, N - k)
            for (int i = 1; i <= k; i++)
                res = res * (N - k + i) / i;
            return (int)res;
        }
    };

3. DP

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