By Long Luo

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. 😉😃💗