# 62. 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 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

# Solution

Approach 1: Recursion.

Approach 2: Combination.

Approach 3: DP.

# Code (Python)

Approach 1:

Approach 2:

Approach 3:

# Code (C++)

Approach 1:

// Time Limit Exceeded.
class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
};

Approach 2:

// C((m-1)+(n-1), (m-1)) = (m-1+n-1)!/(m-1)!(n-1)!
class Solution {
public:
    int uniquePaths(int m, int n) {
        long res = 1;
        for (int i = m; i <= m + n - 2; ++i)
        {
            res = res * i / (i - m + 1);
        }
        return res;
    }
};

Approach 3:

// DP.
class Solution {
public:
    int uniquePaths(int m, int n) {
        long paths[m][n]; // 2D array can't be applied with "= {0}".
        paths[m-1][n-1] = 1;
        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                if (i < m - 1 || j < n - 1)
                    paths[i][j] = 0;
                if (i + 1 < m)
                    paths[i][j] += paths[i+1][j];
                if (j + 1 < n)
                    paths[i][j] += paths[i][j+1];
            }
        }
        return paths[0][0];
    }
};