62

62. Unique Paths (Medium)

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

 

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

 

Constraints:

• 1 <= m, n <= 100

Related Topics:
Math, Dynamic Programming, Combinatorics

Similar Questions:

• Unique Paths II (Medium)
• Minimum Path Sum (Medium)
• Dungeon Game (Medium)
• Minimum Path Cost in a Grid (Medium)
• Minimum Cost Homecoming of a Robot in a Grid (Medium)
• Number of Ways to Reach a Position After Exactly k Steps (Medium)
• Paths in Matrix Whose Sum Is Divisible by K (Medium)

Solution 1. DP

Let dp[i][j] be the number of unique paths to reach (i,j). The answer is dp[m-1][n-1].

dp[i][j] = dp[i][j-1] + dp[i-1][j]   where i >= 1 and j >= 1
dp[0][j] = dp[i][0] = 1

// OJ: https://leetcode.com/problems/unique-paths
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    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][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

Solution 2. DP + Space Optimization

// OJ: https://leetcode.com/problems/unique-paths
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
    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];
    }
};

Solution 3. Math (Combination)

We have m - 1 right operations and n - 1 down operations, m + n - 2 operations in total. The result is the number of different combinations of these operations -- pick m - 1 slots for right operations from m + n - 2 slots.

$$ C(m + n - 2, m - 1) = \dfrac{(m+n-2)!}{(m-1)!\cdot (n-1)!} = \dfrac{m\cdot(m+1)\cdots(m+n-2)}{1\cdot2\cdots(n-1)} $$

// OJ: https://leetcode.com/problems/unique-paths
// Author: github.com/lzl124631x
// Time: O(min(M,N))
// Space: O(1)
class Solution {
public:
    int uniquePaths(int m, int n) {
        if (n > m) swap(n, m);
        long ans = 1;
        for (int i = 1; i <= n - 1; ++i) {
            ans = ans * (m - 1 + i) / i;
        }
        return ans;
    }
};

Solution 4. Math (Combination)

We can use the combination function to compute $C_n^k$

// OJ: https://leetcode.com/problems/unique-paths/
// Author: github.com/lzl124631x
// Time: O(min(M,N))
// Space: O(1)
class Solution {
    int combination(int n, int k) {
        k = min(k, n - k); // Since we loop in range [1, k], we make sure `k` is smaller than `n - k`
        long ans = 1;
        for (int i = 1; i <= k; ++i) ans = ans * (n - k + i) / i;
        return ans;
    }
public:
    int uniquePaths(int m, int n) {
        return combination(m + n - 2, m - 1);
    }
};