# 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

`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

`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:

`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]`

â€‹