A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?


Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:


Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right


Example 2:


Input: m = 7, n = 3
Output: 28

Difficulty: interview

Starter code:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        

Solutions:
class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         def f(n):
             ret = 1
             for i in range(1, n+1):
                 ret *= i
             return ret
         return f(m+n-2)//(f(m-1)*f(n-1))

class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         
         sol = [[0 for j in range(n)] for i in range(m)]
         sol[0][0] = 1
         for i in range(0, m ):
             for j in range(0, n ):
                 if i == 0 or j == 0: sol[i][j] = 1
                 else: sol[i][j] = sol[i-1][j] + sol[i][j-1]
         
         return sol[-1][-1]

class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         counts = {}
         counts[(1, 1)] = 1
         for r in range(2, m+ 1):
             counts[(r, 1)] = 1
         for c in range(2, n + 1):
             counts[(1, c)] = 1
         for i in range(2, m +1):
             for j in range(2, n + 1):
                 counts[(i, j)] = counts[(i - 1, j)] + counts[(i, j -1)]
         return counts[(m, n)]
             
             
     def temp(self, m, n):
         cache = {}
         def go(m, n):
             if m == 1 and n == 1:
                 return 1
             count = 0
             if m > 1:
                 if (m -1, n) not in cache:
                     cache[(m-1, n)] = go(m-1, n)
                 count += cache[(m-1, n)]
             if n > 1:
                 if (m, n - 1) not in cache:
                     cache[(m, n-1)] = go(m, n-1)
                 count += cache[(m, n -1)]
             return count
         return go(m, n)

class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         a = m - 1
         b = n - 1
         ret = 1
         for i in range(b):
             ret = ret * (a+b-i) / (b-i)
         return round(ret)

class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         num_paths = [[0 for _ in range(n)] for _ in range(m)]
         for i in range(m):
             for j in range(n):
                 above = num_paths[i-1][j] if i > 0 else 0
                 left = num_paths[i][j-1] if j > 0 else 0
                 num_paths[i][j] = above + left
                 if i==0 and j==0:
                     num_paths[0][0] = 1
         return num_paths[m-1][n-1]


class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         aux = [[1 for x in range(n)] for x in range(m)]
         for i in range(1, m):
             for j in range(1, n):
                 aux[i][j] = aux[i][j-1]+aux[i-1][j]
         return aux[-1][-1]


class Solution:
     def __init__(self):
         self.dp = [[0 for _ in range(101)] for _ in range(101)]
     def go(self, x, y, m, n):
         if self.dp[x][y] == 0:
             if x == m or y == n:
                 self.dp[x][y] = 0
             elif x == m - 1 and y == n - 1:
                 self.dp[x][y] = 1
             elif x == m - 1 and y == n-1:
                 self.dp[x][y] = 1
             else:
                 self.dp[x][y] = self.go(x+1, y, m, n) + self.go(x, y+1, m, n)
         return self.dp[x][y]
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         return self.go(0, 0, m, n)


class Solution:
     import math
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         if m==1 or n==1:
             return 1
         r,c = m-1, n-1
         return int(math.factorial(r+c)/(math.factorial(r)*math.factorial(c)))


class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         if 0 in (m,n):return 0
         results = [[1] * n]*m
         for i in range(1, m):
             for j in range(1, n):
                 results[i][j] = results[i-1][j] + results[i][j-1]
         return results[m-1][n-1]

class Solution:
     def uniquePaths(self, m, n, memo = None):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         if m == 1 and n == 1:
             return 1
         if m < 1 or n < 1:
             return 0
         
         if not memo:
             memo = [[0 for i in range(n+1)] for j in range(m+1)]
         
         if memo[m][n]:
             return memo[m][n]
         else:
             memo[m][n] = self.uniquePaths(m-1, n, memo) + self.uniquePaths(m, n-1, memo)
             return memo[m][n]
         
         


class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         M = [[1 for _ in range(n)] for _ in range(2)]
         for i in range(m-1, -1, -1):
             for j in range(n-1, -1, -1):
                 if i == m-1 or j == n-1: continue
                 else: M[i%2][j] = M[(i+1)%2][j] + M[i%2][j+1]
         return M[0][0]

class Solution:
     def paths(self,m,n,a,b,memo):
         if m>a or n>b:
             return 0
         if m==a and n==b:
             return 1
         if str(m)+" "+str(n) not in memo:
             memo[str(m)+" "+str(n)] = self.paths(m+1,n,a,b,memo) + self.paths(m,n+1,a,b,memo)
 
         return memo[str(m)+" "+str(n)]
         
         
     def uniquePaths(self, m, n):
         memo =  dict()
         return(self.paths(0,0,m-1,n-1,memo))

class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
     
         matrix = [[0 for j in range(n)] for i in range(m)]
         
         matrix[0][0] = 1
         
         for i in range(m):
             for j in range(n):
                 if i == 0 and j == 0:
                     continue
                 elif i == 0:
                     matrix[i][j] = matrix[i][j-1]
                 elif j == 0:
                     matrix[i][j] = matrix[i-1][j]
                 else:
                     matrix[i][j] = matrix[i][j-1]+matrix[i-1][j]
         return matrix[m-1][n-1]
                     


class Solution:
     def uniquePaths(self, m, n):
         """
         :type m: int
         :type n: int
         :rtype: int
         """
         all=m-1+n-1
         x=1
         y=1
         for i in range(m-1):
             x=x*(all-i)
             y=y*(i+1)
         return x//y