By Long Luo

This article is the solution 3 Approaches: DP, Recursion, Math of Problem 62. Unique Paths.

Here shows 3 Approaches to slove this problem: Dynamic Programming, Recursion, Math.

# Dynamic Programming

The equation is: $$f(i, j) = f(i−1, j) + f(i, j−1)$$.

## Analysis

• Time Complexity: $$O(mn)$$
• Space Complexity: $$O(mn)$$

# Recursion

The DFS is top-down dynamic programming with memoization. If we do ordinary DFS without proper memoization, it will have a TLE error.

## Analysis

• Time Complexity: $$O(mn)$$
• Space Complexity: $$O(mn)$$

# Combination Math

In the process from the top left to the bottom right, we need to move $$m+n-2$$ steps, of which there are $$m-1$$ moves down and $$n-1$$ times to the right.

Therefore, the total number of paths is equal to the number of options for selecting $$m-1$$ downward moves from $$m+n-2$$ moves, that is, the number of combinations:

${\Large C}_{m+n-2}^{m-1} = \binom{m+n-2}{m-1} = \frac{(m+n-2)(m+n-3)\cdots n}{(m-1)!} = \frac{(m+n-2)!}{(m-1)!(n-1)!}$

We can use $$\frac{(m+n-2)(m+n-3)\cdots n}{(m-1)!}$$ to calcuate the number. ​

## Analysis

• Time Complexity: $$O(m)$$
• Space Complexity: $$O(1)$$

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗