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)

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 - 2k = 1for i in range(su,ma,-1):k = k * ifor i in range(1,mi+1):k = k / ireturn int(k)

Time Complexity:O(m+n-2)

Space Complexity:O(1)

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] = 1for j in range(n):dp[0][j] = 1for 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]

â€‹