Problem statement

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?

Example 1

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

Example 2

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 -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3

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

Example 4

Input: m = 3, n = 3
Output: 6

Constraints

• 1 <= m, n <= 100.

• It's guaranteed that the answer will be less than or equal to 2*10^9.

Solution 1: Recursive

At each point, the robot has two ways of moving: right or down. Let P(m,n) is the wanted result. Then you have a recursive relationship:

P(m,n) = P(m-1, n) + P(m, n-1)

If the grid has only one row or only one column, then there is only one possible path.

P(1, n) = P(m, 1) = 1.

We have a recursive implementation.

Code

#include <iostream>
#include <vector>
using namespace std;
int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
int main() {
    std::cout << uniquePaths(3,7) << std::endl;
    std::cout << uniquePaths(7,3) << std::endl;
    std::cout << uniquePaths(3,2) << std::endl;
    std::cout << uniquePaths(3,3) << std::endl;
}

Output:
28
28
3
6

Complexity

• Runtime: O(2^m + 2^n), where m*n is the size of the grid.

• Extra space: O(2^m + 2^n).

Solution 2: Dynamic programming

The recursive implementation repeats a lot of computations.

For example, uniquePaths(2,2) was recomputed in both uniquePaths(2,3) and uniquePaths(3,2) when you compute uniquePaths(3,3).

One way of storing what has been computed is by using dynamic programming.

Code

#include <iostream>
#include <vector>
using namespace std;
int uniquePaths(int m, int n) {
    vector<vector<int> > dp(m, vector<int>(n,1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}
int main() {
    std::cout << uniquePaths(3,7) << std::endl;
    std::cout << uniquePaths(7,3) << std::endl;
    std::cout << uniquePaths(3,2) << std::endl;
    std::cout << uniquePaths(3,3) << std::endl;
}

Output:
28
28
3
6

Complexity

• Runtime: O(m*n), where m*n is the size of the grid.

• Extra space: O(m*n).

Solution 3: Reduced dynamic programming

You can rephrase the relationship inside the loop like this:

"new value" = "old value" + "previous value";

Then you do not have to store all values of all rows.

Code

#include <iostream>
#include <vector>
using namespace std;
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}
int main() {
    std::cout << uniquePaths(3,7) << std::endl;
    std::cout << uniquePaths(7,3) << std::endl;
    std::cout << uniquePaths(3,2) << std::endl;
    std::cout << uniquePaths(3,3) << std::endl;
}

Output:
28
28
3
6

Complexity

• Runtime O(m*n).

• Memory O(n).

Final thought

I am wondering if there is some mathematics behind this problem. Please share your finding if you find a formula for the solution to this problem.

References

• https://leetcode.com/problems/unique-paths/

• https://www.leetsolve.com/62-unique-paths

Get my FREE book "10 Classic Coding Challenges"