# 62. Unique Paths

## Approach 1:  Combinatorics

Let us assume that the `m = 3` and `n = 3`

The path will then always be 4 moves long: DDRR, DRDR, RDRD..... where R means Right, and D means Down.

On observation you can see that the path length will always be `m-1` R's and `n-1` D's to reach the bottom corner and the total path length is `m+n-2`

We can convert this problem into a linear one: 

> Given a string of length `m + n - 2` fill it with `m-1` R's and `n-1` D's

Using combinatorics we can say that it is: `m+n-2` choose `m-1` i.e. `(m+n-2)C(m-1)` which is evaluated as the answer below

```python
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        di = {0:1, 1:1, 2:2}
        def factorial(n):
            if n in di:
                return di[n]
            else:
                di[n] = n*factorial(n-1)
                return di[n]
        return int(factorial(m+n-2)/(factorial(m-1)*factorial(n-1)))
```

> **Time Complexity:** *O(m+n-2)* 
>
> **Space Complexity:** *O(m+n-2)* 

## Approach 2: Use multiplication instead of factorial

Same math as above but just a different way of evaluation

Instead of using a memo-ised factorial function we can simply calculate it as below since we know the values of `m` and `n`. This solution is more memory efficient than above

```python
class Solution:
    def uniquePaths(self, m, n):
        """
        https://leetcode.com/problems/unique-paths/description/
        :type m: int
        :type n: int
        :rtype: int
        """
        ma, mi = max(m-1,n-1) , min(m-1,n-1)
        su = m + n - 2
        k = 1
        for i in range(su,ma,-1):
            k = k * i
        for i in range(1,mi+1):
            k = k / i
        return int(k)
```

> **Time Complexity:** *O(m+n-2)* 
>
> **Space Complexity:** *O(1)* 

## Approach 3: Dynamic Programming

Since we can only move in 2 directions, `dp[i][j] = dp[i-1][j] + dp[i][j-1]`

where `dp[i][j]` stands for the total number of paths till location(i,j)

As for the initial conditions: `dp[i][0] = 1` for all `i < m` and `dp[0][j]` for all j < n

Using this we can get the total number of paths as follows:

```python
class Solution:
    def uniquePaths(self, m, n):
        """
        https://leetcode.com/problems/unique-paths/description/
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1]*n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]
```