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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics

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

Solutions:
class Solution:

	def uniquePaths(self, m, n):

		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):
		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):
		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):
		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):
		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):
		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):
		return self.go(0, 0, m, n)


class Solution:
	import math

	def uniquePaths(self, m, n):
		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):
		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):
		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):
		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):
		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):
		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