62. Unique Paths

Description of Problem

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 * 10^9.

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

Solution

Tags: Permutation and Combination Dynamic Programming

Explanation

The examples of the problem gives us hints. The number of unique path is the number of unique combination of Move Right and Move Down.

Thus, the solution is \( \frac{(m-1+n-1)!}{(m-1)!(n-1)!} \).

However, the calculation of the number will cause the integer overflow. Therefore, we have to use DP to calculate the number:

\[ \begin{align} P_{m,n} & = \frac{(m+n)!}{m! \ n!} \\ P_{m-1,n} + P_{m,n-1} & = \frac{(m-1+n)!}{(m-1)! \ n!} + \frac{(m+n-1)!}{m! \ (n-1)!} \\ & = \frac{m \ (m-1+n)!}{m \ (m-1)! \ n!} + \frac{(m+n-1)! \ n}{m! \ (n-1)! \ n} \\ & = \frac{m \ (m-1+n)! + (m+n-1)! \ n}{m! \ n!} \\ & = \frac{(m+n) \ (m-1+n)!}{m! \ n!} \\ & = P_{m,n} \end{align} \]

Code (Rust)

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        if m <= 1 || n <= 1 {
            return 1;
        }

        let (m,n) = (m as usize, n as usize);

        let mut dp = vec![ vec![1;n];m ];

        for i in 1..m {
            for j in 1..n{
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        
        return dp[m-1][n-1] as i32;
    }
}

Complexity

Time Complexity

• \(T(m,n) = \Theta(m,n)\)

Auxiliary Space

• \(S(m,n) = O(m,n)\)