Unique Paths

Problem

There is an m x n grid where you are allowed to move either down or to the right at any point in time.

Given the two integers m and n, return the number of possible unique paths that can be taken from the top-left corner of the grid (grid[0][0]) to the bottom-right corner (grid[m - 1][n - 1]).

You may assume the output will fit in a 32-bit integer.

Examples

Example 1:

Input: m = 3, n = 6

Output: 21

Example 2:

Input: m = 3, n = 3

Output: 6

Constraints

• 1 <= m, n <= 100

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Solution

dfs(r, c) is the number of paths starting at (r,c). Once we know this value, we store. There is a closed form solution, but it requires to remember how to compute binomial numbers without over/under flow

class Solution {
    int factorial(int x) {
        return x <= 1 ? 1 : x * factorial(x-1);
    }
public:
    int uniquePaths(int m, int n) {
        // Exact but need to be careful with overflowing
        // return factorial(m + n - 2) / (factorial(n-1) * factorial(m - 1));
 
        std::vector<int> memo(m * n, -1);
        // dfs(r, c) is how many paths to goal from (r, c)
        std::function<int(int, int)> dfs;
        dfs = [&](int r, int c) -> int {
            // Out of bounds
            if (r >= m || c >= n) { return 0; }
            // At goal
            if (r == m - 1 && c == n - 1) { return 1; }
            // Check if we know the result
            if (memo[r * n + c] != -1) { return memo[r * n + c]; }
            // Otherwise, result is sum of paths going down and left
            auto res = dfs(r + 1, c) + dfs(r, c + 1);
            memo[r * n + c] = res;
            return res;
        };
        return dfs(0, 0);
    }
};