Given a A X B matrix with your initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position.
Note: Possible moves can be either down or right at any point in time, i.e., we can move to matrix[i+1][j] or matrix[i][j+1] from matrix[i][j].
Example 1:
Input:
A = 2, B = 2
Output: 2
Explanation: There are only two unique
paths to reach the end of the matrix of
size two from the starting cell of the
matrix.
Example 2:
Input:
A = 3, B = 4
Output: 10
Explanation: There are only 10 unique
paths to reach the end of the matrix of
size two from the starting cell of the
matrix.
Your Task:
Complete NumberOfPath() function which takes 2 arguments(A and B) and returns the number of unique paths from top-left to the bottom-right cell.
Expected Time Complexity: O(A*B).
Expected Auxiliary Space: O(A*B).
Constraints:
1 ≤ A ≤ 16
1 ≤ B ≤ 16

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



   

class Solution:

    #Function to find total number of unique paths.

    def NumberOfPaths(self,a, b):

        #code here

Solutions:
class Solution:

	def NumberOfPaths(self, a, b):
		if a > b:
			return self.NumberOfPaths(b, a)
		x = a + b - 2
		ans = 1
		for i in range(1, a):
			ans = ans * x
			ans = ans / i
			x = x - 1
		return int(ans)


class Solution:

	def NumberOfPaths(self, a, b):
		vis = [[-1 for i in range(b)] for j in range(a)]

		def funcall(x, y, vis):
			if x == a - 1 or y == b - 1:
				return 1
			if vis[x][y] != -1:
				return vis[x][y]
			vis[x][y] = funcall(x + 1, y, vis) + funcall(x, y + 1, vis)
			return vis[x][y]
		return funcall(0, 0, vis)


class Solution:

	def NumberOfPaths(self, a, b):

		def solve(i, j, a, b):
			if i == a or j == b:
				return 0
			if i == a - 1 and j == b - 1:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = solve(i + 1, j, a, b) + solve(i, j + 1, a, b)
			return dp[i][j]
		dp = [[-1 for i in range(b)] for i in range(a)]
		return solve(0, 0, a, b)


class Solution:

	def NumberOfPaths(self, a, b):
		dp = []
		for i in range(a):
			temp = []
			for j in range(b):
				temp.append(0)
			dp.append(temp)
		for i in range(a):
			for j in range(b):
				if i == 0 and j == 0:
					dp[i][j] = 1
				elif i == 0:
					dp[i][j] += dp[i][j - 1]
				elif j == 0:
					dp[i][j] += dp[i - 1][j]
				else:
					dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
		return dp[-1][-1]


class Solution:

	def NumberOfPaths(self, a, b):
		dp = [[-1 for _ in range(b)] for _ in range(a)]
		for i in range(a):
			for j in range(b):
				if i == 0 and j == 0:
					dp[i][j] = 1
				else:
					up = 0
					if i > 0:
						up = dp[i - 1][j]
					left = 0
					if j > 0:
						left = dp[i][j - 1]
					dp[i][j] = up + left
		return dp[a - 1][b - 1]


class Solution:

	def NumberOfPaths(self, a, b):
		mat = []
		for i in range(a):
			temp = []
			for j in range(b):
				temp.append(-1)
			mat.append(temp)
		return self.find(0, 0, a, b, mat)

	def find(self, r, c, a, b, mat):
		if mat[r][c] != -1:
			return mat[r][c]
		if r == a or c == b:
			return 0
		if r == a - 1 or c == b - 1:
			return 1
		mat[r][c] = self.find(r + 1, c, a, b, mat) + self.find(r, c + 1, a, b, mat)
		return mat[r][c]


class Solution:

	def NumberOfPaths(self, a, b):
		t = [[1 for x in range(b)] for y in range(a)]
		for i in range(1, a):
			for j in range(1, b):
				t[i][j] = t[i - 1][j] + t[i][j - 1]
		return t[-1][-1]


class Solution:

	def NumberOfPaths(self, a, b):
		mat = [[0 for i in range(b)] for j in range(a)]
		dp = [[-1 for i in range(b)] for j in range(a)]

		def dfs(i, j):
			if i == a - 1 or j == b - 1:
				return 1
			if i < 0 or i >= a or j < 0 or (j >= b):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = dfs(i + 1, j) + dfs(i, j + 1)
			return dp[i][j]
		return dfs(0, 0)


class Solution:

	def NumberOfPaths(self, m, n):
		dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]

		def memo(i, j):
			if i == 0 or j == 0:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = memo(i - 1, j) + memo(i, j - 1)
			return dp[i][j]
		return memo(m - 1, n - 1)


class Solution:

	def NumberOfPaths(self, a, b):
		dp = [[0 for i in range(b)] for j in range(a)]
		for i in range(a):
			dp[i][0] = 1
		for j in range(b):
			dp[0][j] = 1
		for i in range(1, a):
			for j in range(1, b):
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[a - 1][b - 1]


class Solution:

	def NumberOfPaths(self, m, n):
		dp = [[1] * n for _ in range(m)]
		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]


class Solution:

	def NumberOfPaths(self, a, b):
		dp = [[-1 for j in range(b)] for i in range(a)]
		if a == 1 and b == 1:
			return 1
		if a == 1:
			return 1 + self.Number(a, b - 1, dp)
		if b == 1:
			return 1 + self.Number(a - 1, b, dp)
		return 2 + self.Number(a - 1, b, dp) + self.Number(a, b - 1, dp)

	def Number(self, a, b, dp):
		if a != 1 and b == 1:
			return 0
		elif a == 1 and b != 1:
			return 0
		elif a == 1 and b == 1:
			return 0
		if dp[a - 1][b - 1] != -1:
			return dp[a - 1][b - 1]
		if a != 1 and b != 1:
			dp[a - 1][b - 1] = 1 + self.Number(a - 1, b, dp) + self.Number(a, b - 1, dp)
			return dp[a - 1][b - 1]


class Solution:

	def NumberOfPaths(self, m, n):
		dp = [[0] * n for _ in range(m)]
		dp[-1][-1] = 1
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if i == m - 1 and j == n - 1:
					continue
				if i == m - 1 or j == n - 1:
					dp[i][j] = 1
					continue
				dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
		return dp[0][0]


from functools import lru_cache

class Solution:

	def NumberOfPaths(self, m, n):

		@lru_cache(None)
		def recursion(i, j):
			if i == m - 1 and j == n - 1:
				return 1
			if i < 0 or i >= m or j < 0 or (j >= n):
				return 0
			return recursion(i + 1, j) + recursion(i, j + 1)
		return recursion(0, 0)


class Solution:

	def NumberOfPaths(self, a, b):
		dp = [[0 for _ in range(b)] for _ in range(a)]
		for i in range(a):
			for j in range(b):
				if i == 0 or j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[a - 1][b - 1]


class Solution:

	def NumberOfPaths(self, m, n):
		dp = [[-1 for j in range(n)] for i in range(m)]

		def helper(i, j):
			if i == 0 and j == 0:
				return 1
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			up = helper(i - 1, j)
			left = helper(i, j - 1)
			dp[i][j] = up + left
			return dp[i][j]
		return helper(m - 1, n - 1)


class Solution:

	def NumberOfPaths(self, a, b):
		tabarray = [[0 for i in range(b)] for j in range(a)]
		tabarray[0][0] = 1
		for i in range(a):
			for j in range(b):
				if j > 0:
					tabarray[i][j] += tabarray[i][j - 1]
				if i > 0:
					tabarray[i][j] += tabarray[i - 1][j]
		return tabarray[a - 1][b - 1]


class Solution:

	def NumberOfPaths(self, a, b):

		def path(i, j, dp):
			if i == 0 and j == 0:
				dp[i][j] = 1
				return dp[i][j]
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != 0:
				return dp[i][j]
			up = path(i - 1, j, dp)
			left = path(i, j - 1, dp)
			dp[i][j] = up + left
			return dp[i][j]
		dp = [[0 for i in range(b)] for i in range(a)]
		return path(a - 1, b - 1, dp)


class Solution:

	def NumberOfPaths(self, a, b):

		def fact(n):
			if n <= 1:
				return 1
			return n * fact(n - 1)
		r = a - 1
		c = b - 1
		total = r + c
		return fact(total) // (fact(total - r) * fact(r))


class Solution:
	count = 0
	dp = []

	def gen(self, a, b, x, y):
		if x > a or y > b:
			return 0
		if x == a and y == b:
			return 1
		if self.dp[x][y] != -1:
			return self.dp[x][y]
		l = self.gen(a, b, x + 1, y)
		r = self.gen(a, b, x, y + 1)
		self.dp[x][y] = l + r
		return self.dp[x][y]

	def NumberOfPaths(self, a, b):
		self.dp = []
		for i in range(a):
			arr = []
			for j in range(b):
				arr.append(-1)
			self.dp.append(arr)
		a = self.gen(a - 1, b - 1, 0, 0)
		return a


class Solution:

	def solve(self, N, M, i, j, vis, dp):
		if i == N and j == M:
			return 1
		if i < 0 or i > N or j < 0 or (j > M):
			return 0
		if vis[i][j] == True:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		count = 0
		vis[i][j] = True
		for (x, y) in [(0, 1), (1, 0)]:
			count += self.solve(N, M, i + x, j + y, vis, dp)
		vis[i][j] = False
		dp[i][j] = count
		return dp[i][j]

	def NumberOfPaths(self, a, b):
		if a == 1 or b == 1:
			return 1
		dp = [[-1 for _ in range(b)] for _ in range(a)]
		vis = [[False for _ in range(b)] for _ in range(a)]
		self.solve(a - 1, b - 1, 0, 0, vis, dp)
		return dp[0][0]


from functools import lru_cache

@lru_cache(maxsize=None)
def fact(n):
	if n == 0 or n == 1:
		return 1
	else:
		return n * fact(n - 1)

class Solution:

	def NumberOfPaths(self, a, b):
		return int(fact(a + b - 2) / (fact(a - 1) * fact(b - 1)))


class Solution:

	def NumberOfPaths(self, a, b):
		n = a - 1
		m = b - 1
		dp = [[0] * (m + 1) for i in range(n + 1)]
		dp[n][m] = 1
		for i in range(n, -1, -1):
			for j in range(m, -1, -1):
				if i == n and j == m:
					continue
				if i + 1 <= n:
					dp[i][j] += dp[i + 1][j]
				if j + 1 <= m:
					dp[i][j] += dp[i][j + 1]
				dp[i][j] = dp[i][j]
		return dp[0][0]


class Solution:

	def NumberOfPaths(self, a, b):
		l = []
		if a == 1 and b == 1:
			return 1
		for i in range(a + 1):
			l += [[0] * (b + 1)]
		for i in range(a):
			for j in range(b):
				if i == 0 and j == 0:
					l[i][j] = 0
				elif i == 0 or j == 0:
					l[i][j] = 1
		for i in range(1, a):
			for j in range(1, b):
				l[i][j] = l[i - 1][j] + l[i][j - 1]
		return l[a - 1][b - 1]


from math import factorial

class Solution:

	def NumberOfPaths(self, a, b):
		return factorial(a + b - 2) // factorial(a - 1) // factorial(b - 1)


class Solution:

	def NumberOfPaths(self, a, b):

		def uniquePath(m, n, i, j, dp):
			if i == m - 1 and j == n - 1:
				return 1
			if i == m or j == n:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			down = uniquePath(m, n, i + 1, j, dp)
			right = uniquePath(m, n, i, j + 1, dp)
			dp[i][j] = down + right
			return down + right
		dp = [[-1 for _ in range(b)] for _ in range(a)]
		return uniquePath(a, b, 0, 0, dp)


class Solution:

	def helper(self, a, b, i, j, memo):
		if a - 1 == i and b - 1 == j:
			return 1
		if (i, j) in memo:
			return memo[i, j]
		directions = [(0, 1), (1, 0)]
		ans = 0
		for d in directions:
			(newr, newc) = (d[0] + i, d[1] + j)
			if newr < 0 or newr >= a or newc < 0 or (newc >= b):
				continue
			ans += self.helper(a, b, newr, newc, memo)
		memo[i, j] = ans
		return ans

	def NumberOfPaths(self, a, b, i=0, j=0, memo=dict()):
		memo = dict()
		return self.helper(a, b, 0, 0, memo)


class Solution:

	def NumberOfPaths(self, a, b):

		def calc(r, c, dp):
			if dp[r][c] != -1:
				return dp[r][c]
			if r == 0 and c == 0:
				return 1
			c1 = 0
			if r - 1 >= 0:
				c1 = calc(r - 1, c, dp)
			c2 = 0
			if c - 1 >= 0:
				c2 = calc(r, c - 1, dp)
			dp[r][c] = c1 + c2
			return dp[r][c]
		dp = [[-1 for i in range(b)] for j in range(a)]
		return calc(a - 1, b - 1, dp)


class Solution:

	def NumberOfPaths(self, a, b):
		prev = [0 for i in range(b)]
		curr = [0 for i in range(b)]
		for i in range(a):
			for j in range(b):
				up = 0
				left = 0
				if i == 0 and j == 0:
					curr[j] = 1
				else:
					if i > 0:
						up = prev[j]
					if j > 0:
						left = curr[j - 1]
					curr[j] = up + left
			prev = curr
		return prev[b - 1]


class Solution:

	def NumberOfPaths(self, A, B):
		dp = [[0 for _ in range(0, B + 1)] for i in range(0, A + 1)]
		dp[0][0] = 1
		for i in range(0, A):
			for j in range(0, B):
				if i > 0 and j > 0:
					dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
				elif i > 0:
					dp[i][j] += dp[i - 1][j]
				elif j > 0:
					dp[i][j] += dp[i][j - 1]
		return dp[A - 1][B - 1]


import math

class Solution:

	def NumberOfPaths(self, a, b):
		t = a + b - 2
		r = a - 1
		ans = 1
		for i in range(1, a - 1 + 1):
			ans = ans * (t - r + i) // i
		return ans


class Solution:

	def func(self, row, col, dp):
		if row == 0 and col == 0:
			return 1
		if row < 0 or col < 0:
			return 0
		if dp[row][col] != -1:
			return dp[row][col]
		up = self.func(row - 1, col, dp)
		left = self.func(row, col - 1, dp)
		dp[row][col] = up + left
		return dp[row][col]

	def NumberOfPaths(self, m, n):
		dp = [[-1 for i in range(n)] for j in range(m)]
		return self.func(m - 1, n - 1, dp)


class Solution:

	def NumberOfPaths(self, a, b):
		dp = [[-1 for i in range(b + 1)] for j in range(a + 1)]

		def helper(i, j, m, n, dp):
			if i == m - 1 and j == n - 1:
				return 1
			if i >= m or j >= n:
				return 0
			if dp[i + 1][j] == -1:
				ans1 = helper(i + 1, j, m, n, dp)
				dp[i + 1][j] = ans1
			else:
				ans1 = dp[i + 1][j]
			if dp[i][j + 1] == -1:
				ans2 = helper(i, j + 1, m, n, dp)
				dp[i][j + 1] = ans2
			else:
				ans2 = dp[i][j + 1]
			return ans1 + ans2
		return helper(0, 0, a, b, dp)


class Solution:

	def NumberOfPaths(self, m, n):

		def solveTab(i, j):
			dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
			for i in range(m + 1):
				dp[i][0] = 1
			for j in range(n + 1):
				dp[0][j] = 1
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					up = dp[i - 1][j]
					left = dp[i][j - 1]
					dp[i][j] = up + left
			return dp[m - 1][n - 1]
		return solveTab(m, n)


class Solution:

	def NumberOfPaths(self, a, b):
		grid = [[1 for i in range(b)] for j in range(a)]
		count = 0
		dp = [[-1 for i in range(b)] for j in range(a)]
		return self.helper(0, 0, grid, a, b, dp)

	def helper(self, row, col, grid, A, B, dp):
		count = 0
		if row == A - 1 and col == B - 1:
			return 1
		if dp[row][col] != -1:
			return dp[row][col]
		dRow = [0, 1]
		dCol = [1, 0]
		for i in range(2):
			nrow = row + dRow[i]
			ncol = col + dCol[i]
			if nrow >= 0 and nrow < A and (ncol >= 0) and (ncol < B):
				count += self.helper(nrow, ncol, grid, A, B, dp)
		dp[row][col] = count
		return dp[row][col]


class Solution:

	def NumberOfPaths(self, a, b):
		mat = [[0 for cols in range(b)] for rows in range(a)]
		for i in range(a):
			mat[i][b - 1] = 1
		for i in range(b):
			mat[a - 1][i] = 1
		for i in range(a - 2, -1, -1):
			for j in range(b - 2, -1, -1):
				mat[i][j] = mat[i + 1][j] + mat[i][j + 1]
		return mat[0][0]


class Solution:

	def fun(self, i, j, dp):
		if i == 0 and j == 0:
			return 1
		elif i < 0 or j < 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		up = self.fun(i - 1, j, dp)
		left = self.fun(i, j - 1, dp)
		dp[i][j] = up + left
		return dp[i][j]

	def NumberOfPaths(self, a, b):
		dp = [[-1 for i in range(b)] for j in range(a)]
		for i in range(a):
			for j in range(b):
				if i == 0 and j == 0:
					dp[i][j] = 1
				else:
					(up, left) = (0, 0)
					if i > 0:
						up = dp[i - 1][j]
					if j > 0:
						left = dp[i][j - 1]
					dp[i][j] = up + left
		return dp[a - 1][b - 1]


class Solution:

	def NumberOfPaths(self, a, b):
		matrix = [[1 for i in range(b + 1)] for j in range(a + 1)]
		for i in range(a - 2, -1, -1):
			for j in range(b - 2, -1, -1):
				matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1]
		return matrix[0][0]


class Solution:

	def NumberOfPaths(self, m, n):
		p = [[1 for i in range(n)] for j in range(m)]
		for i in range(m - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				p[i][j] = p[i + 1][j] + p[i][j + 1]
		return p[0][0]


class Solution:

	def NumberOfPaths(self, a, b):
		prevRow = [0] * b
		for r in range(a - 1, -1, -1):
			currRow = [0] * b
			currRow[b - 1] = 1
			for c in range(b - 2, -1, -1):
				currRow[c] = currRow[c + 1] + prevRow[c]
			prevRow = currRow
		return prevRow[0]


class Solution:

	def NumberOfPaths(self, m, n):
		if not m or not n:
			return 0
		cur = [1] * n
		for i in range(1, m):
			for j in range(1, n):
				cur[j] += cur[j - 1]
		return cur[-1]


class Solution:

	def NumberOfPaths(self, m, n):
		prev = [0] * n
		for i in range(m):
			temp = [0] * n
			for j in range(n):
				if i == 0 and j == 0:
					temp[j] = 1
					continue
				up = prev[j]
				left = temp[j - 1]
				temp[j] = up + left
			prev = temp
		return prev[-1]


class Solution:

	def NumberOfPaths(self, m, n):
		dp = [[-1] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if i == 0 and j == 0:
					dp[i][j] = 1
					continue
				else:
					up = 0
					left = 0
					if i > 0:
						up = dp[i - 1][j]
					if j > 0:
						left = dp[i][j - 1]
					dp[i][j] = up + left
		return dp[m - 1][n - 1]


import math

class Solution:

	def NumberOfPaths(self, a, b):
		prev = [1] * b
		for i in range(a - 1):
			temp = []
			for j in range(b):
				if j == 0:
					temp.append(prev[j])
				else:
					temp.append(temp[j - 1] + prev[j])
			prev = temp
		return prev[b - 1]


import math

class Solution:

	def NumberOfPaths(self, a, b):
		total_moves = a + b - 2
		down_moves = a - 1
		right_moves = b - 1
		return math.factorial(total_moves) // (math.factorial(down_moves) * math.factorial(right_moves))


class Solution:

	def NumberOfPaths(self, a, b):
		r = [1] * a
		for i in range(b - 1):
			nr = [1] * a
			for j in range(a - 2, -1, -1):
				nr[j] = nr[j + 1] + r[j]
			r = nr
		return r[0]


class Solution:

	def NumberOfPaths(self, m, n):
		row = [1] * n
		for i in range(m - 1):
			newrow = [1] * n
			for j in range(n - 2, -1, -1):
				newrow[j] = newrow[j + 1] + row[j]
			row = newrow
		return row[0]


from math import factorial

class Solution:

	def NumberOfPaths(self, a, b):
		a -= 1
		b -= 1
		num = factorial(a + b)
		deno = factorial(a) * factorial(b)
		return num // deno


class Solution:

	def NumberOfPaths(self, a, b):
		dp = [[0 for _ in range(b + 1)] for _ in range(a + 1)]
		dp[1][1] = 1
		for i in range(1, a + 1):
			for j in range(1, b + 1):
				if i == 1 and j == 1:
					continue
				if i == 1:
					dp[i][j] = dp[i][j - 1]
				elif j == 1:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[a][b]


class Solution:

	def path(self, i, j, dp):
		if i == 0 and j == 0:
			return 1
		if i < 0 or j < 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		up = self.path(i - 1, j, dp)
		left = self.path(i, j - 1, dp)
		dp[i][j] = up + left
		return dp[i][j]

	def pathTab(self, m, n):
		dp = [[-1] * n for i in range(m)]
		dp[0][0] = 1
		for i in range(m):
			for j in range(n):
				if i == 0 and j == 0:
					dp[i][j] = 1
				else:
					(up, left) = (0, 0)
					if i > 0:
						up = dp[i - 1][j]
					if j > 0:
						left = dp[i][j - 1]
					dp[i][j] = up + left
		return dp[m - 1][n - 1]

	def NumberOfPaths(self, a, b):
		return self.pathTab(a, b)


class Solution:

	def NumberOfPaths(self, a, b):

		def recur(row, col):
			if row == 0 and col == 0:
				return 1
			if row < 0 or col < 0:
				return 0
			if dp[row][col] != -1:
				return dp[row][col]
			up = recur(row - 1, col)
			left = recur(row, col - 1)
			dp[row][col] = up + left
			return dp[row][col]
		dp = [[-1] * b for i in range(a)]
		return recur(a - 1, b - 1)


class Solution:

	def fact(self, a):
		res = 1
		for x in range(1, a + 1):
			res = res * x
		return res

	def NumberOfPaths(self, a, b):
		return self.fact(a + b - 2) // (self.fact(a - 1) * self.fact(b - 1))