The task is to count all the possible paths from top left to bottom right of a m X n matrix with the constraints that from each cell you can either move only to right or down.
Example 1:
Input: m = 2, n = 2
Output: 2 
Explanation: Two possible ways are
RD and DR.  
Example 2:
Input: m = 3, n = 3
Output: 6
Explanation: Six possible ways are
RRDD, DDRR, RDDR, DRRD, RDRD, DRDR. 
Your Task:  
You dont need to read input or print anything. Complete the function numberOfPaths() which takes m and n as input parameter and returns count all the possible paths.The answer may be very large, compute the answer modulo 10^{9} + 7.
Expected Time Complexity: O(m*n)
Expected Auxiliary Space: O(m*n)
Constraints:
1 <= m <=100
1 <= n <=100

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Combinatorics

Starter code: #User function Template for python3

class Solution:

	def numberOfPaths(self, m, n):

		# code here



Solutions:
class Solution:

	def fin(self, x, y, m, n, dp):
		if x >= n or y >= m:
			return 0
		if x == n - 1 and y == m - 1:
			return 1
		if dp[x][y] != -1:
			return dp[x][y]
		else:
			dp[x][y] = (self.fin(x + 1, y, m, n, dp) + self.fin(x, y + 1, m, n, dp)) % int(1000000000.0 + 7)
			return dp[x][y]

	def numberOfPaths(self, m, n):
		x = 0
		y = 0
		dp = [[-1 for i in range(m)] for j in range(n)]
		ans = self.fin(x, y, m, n, dp)
		return ans


class Solution:

	def numberOfPaths(self, m, n):
		arr = [[0 for i in range(n)] for j in range(m)]
		for i in range(0, m):
			for j in range(0, n):
				if i == m - 1 or j == n - 1:
					arr[i][j] = 1
		for i in range(m - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				arr[i][j] = (arr[i + 1][j] + arr[i][j + 1]) % 1000000007
		return arr[0][0]


from math import factorial as fact

class Solution:

	def numberOfPaths(self, m, n):
		return fact(m + n - 2) // (fact(n - 1) * fact(m - 1)) % (10 ** 9 + 7)


class Solution:

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


from math import factorial

class Solution:

	def numberOfPaths(self, m, n):
		return factorial(m + n - 2) // (factorial(n - 1) * factorial(m - 1)) % 1000000007


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[0 for i in range(n)] for j in range(m)]
		for i in range(n):
			dp[0][i] = 1
		for i in range(m):
			dp[i][0] = 1
		for i in range(1, m):
			for j in range(1, n):
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % (10 ** 9 + 7)
		return dp[m - 1][n - 1]


import math

class Solution:

	def numberOfPaths(self, m, n):
		a = math.factorial(m + n - 2)
		c = math.factorial(m - 1)
		d = math.factorial(n - 1)
		return a // (c * d) % (10 ** 9 + 7)


import math

class Solution:

	def numberOfPaths(self, m, n):
		l = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if i == 1 and j == 1:
					l[i][j] = 1
				else:
					l[i][j] = l[i - 1][j] + l[i][j - 1]
		return l[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[None for j in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n):
				if i == 0 or j == 0:
					dp[i][j] = 1
					continue
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[-1][-1] % 1000000007


import math

class Solution:

	def numberOfPaths(self, m, n):
		a = math.factorial(m + n - 2)
		b = math.factorial(n - 1)
		c = math.factorial(m - 1)
		d = b * c
		return a // d % 1000000007


import math

class Solution:

	def numberOfPaths(self, m, n):
		num = math.factorial(m + n - 2)
		den1 = math.factorial(m - 1)
		den2 = math.factorial(n - 1)
		return num // (den1 * den2) % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		dp = []
		for x in range(m):
			dp.append([0] * n)
		for x in range(len(dp)):
			for y in range(len(dp[0])):
				if x == 0 or y == 0:
					dp[x][y] = 1
				else:
					dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[0 for i in range(n)] for j in range(m)]
		dp[0][0] = 1
		for i in range(m):
			for j in range(n):
				if i == 0 and j == 0:
					continue
				elif i > 0 and j > 0:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
				elif j == 0:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i][j - 1]
		return dp[m - 1][n - 1] % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[-1] * n for i in range(m)]
		visited = [[-1] * n for i in range(m)]

		def pospath(i, j, m, n):
			if i < 0 or j < 0 or i >= m or (j >= n) or (visited[i][j] == 1):
				return 0
			if i == m - 1 and j == n - 1:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			visited[i][j] = 1
			val = 0
			val += pospath(i, j + 1, m, n)
			val = val % 1000000007
			val += pospath(i + 1, j, m, n)
			val = val % 1000000007
			dp[i][j] = val
			visited[i][j] = -1
			return val
		return pospath(0, 0, m, n)


class Solution:

	def numberOfPaths(self, m, n):

		def dfs(i, j, dp):
			key = str(i) + ',' + str(j)
			if key in dp:
				return dp[key]
			if i == m - 1 and j == n - 1:
				return 1
			if i >= m or j >= n:
				return 0
			dp[key] = dfs(i + 1, j, dp) + dfs(i, j + 1, dp)
			return dp[key]
		res = dfs(0, 0, {})
		return res % (10 ** 9 + 7)


class Solution:

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

	def solve(self, i, j, paths, 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]
		paths += self.solve(i - 1, j, paths, dp) + self.solve(i, j - 1, paths, dp)
		dp[i][j] = paths
		return dp[i][j] % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		table = [[1 for i in range(n)] for j in range(m)]
		for i in range(1, m):
			for j in range(1, n):
				table[i][j] = table[i][j - 1] % 1000000007 + table[i - 1][j] % 1000000007
		return table[-1][-1] % 1000000007


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]) % 1000000007
		return dp[m - 1][n - 1]


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[-1] * n for _ in range(m)]

		def dfs(i, j):
			nonlocal dp
			if not (0 <= i < m and 0 <= j < n):
				return 0
			if i == m - 1 and j == n - 1:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = dfs(i, j + 1) + dfs(i + 1, j)
			return dp[i][j]
		return dfs(0, 0) % 1000000007


class Solution:

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

		def dfs(i, j):
			if i >= m or j >= n or i < 0 or (j < 0):
				return 0
			if i == m - 1 and j == n - 1:
				return 1
			if l[i][j] != -1:
				return l[i][j]
			l[i][j] = dfs(i, j + 1) + dfs(i + 1, j)
			return l[i][j] % 1000000007
		return dfs(0, 0) % 1000000007


class Solution:

	def numberOfPaths(self, m, n):
		a = []
		for i in range(m):
			p = []
			for j in range(n):
				if j == 0 or i == 0:
					p.append(1)
				else:
					p.append(0)
			a.append(p)
		for i in range(1, m):
			for j in range(1, n):
				a[i][j] = a[i - 1][j] + a[i][j - 1]
		return a[m - 1][n - 1] % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def numberOfPaths(self, m, n):

		@lru_cache(maxsize=128)
		def helper(a, b):
			if a == 1 or b == 1:
				return 1
			return helper(a - 1, b) + helper(a, b - 1)
		return helper(m, n) % 1000000007


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[0 for i in range(n)] for j in range(m)]
		dp[0][0] = 1
		for i in range(m):
			for j in range(n):
				if i != 0 or j != 0:
					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][j - 1]
					else:
						dp[i][j] = dp[i - 1][j]
		return dp[m - 1][n - 1] % 1000000007


class Solution:

	def numberOfPaths(self, m, n):
		d = {}

		def helper(a, b):
			if a == 1 or b == 1:
				return 1
			k = str(a) + ',' + str(b)
			if k in d:
				return d[k]
			else:
				d[k] = helper(a - 1, b) + helper(a, b - 1)
				return d[k]
		return helper(m, n) % 1000000007


class Solution:

	def numberOfPaths(self, m, n):
		p = 10 ** 9 + 7
		count = [[0 for x in range(n)] for y in range(m)]
		for i in range(m):
			count[i][0] = 1
		for j in range(n):
			count[0][j] = 1
		for i in range(1, m):
			for j in range(1, n):
				count[i][j] = count[i - 1][j] + count[i][j - 1]
		return count[m - 1][n - 1] % p


class Solution:

	def numberOfPaths(self, m, n):
		mod = 10 ** 9 + 7
		dp = [[-1 for i in range(n)] for j in range(m)]

		def paths(dp, m, n):
			if m == 0 or n == 0:
				return 1
			if dp[m][n] == -1:
				dp[m][n] = paths(dp, m - 1, n) + paths(dp, m, n - 1)
			return dp[m][n] % mod
		return paths(dp, m - 1, n - 1) % mod


class Solution:

	def recu(self, row, col, dp, m, n):
		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]
		right = self.recu(row, col - 1, dp, m, n)
		down = self.recu(row - 1, col, dp, m, n)
		dp[row][col] = right + down
		return right + down

	def numberOfPaths(self, m, n):
		mod = 10 ** 9 + 7
		dp = [[-1] * n for i in range(m)]
		return self.recu(m - 1, n - 1, dp, m, n) % mod


class Solution:

	def getPaths(self, x_index, y_index, row, col, dp):
		if x_index == row or y_index == col:
			return 0
		if x_index == row - 1 and y_index == col - 1:
			return 1
		if dp[x_index][y_index] != -1:
			return dp[x_index][y_index]
		dp[x_index][y_index] = self.getPaths(x_index + 1, y_index, row, col, dp) + self.getPaths(x_index, y_index + 1, row, col, dp)
		return dp[x_index][y_index]

	def numberOfPaths(self, m, n):
		dp = [[-1 for i in range(n)] for j in range(m)]
		return self.getPaths(0, 0, m, n, dp) % (pow(10, 9) + 7)


class Solution:

	def numberOfPaths(self, m, n):
		matrix = [[0 for i in range(n)] for j in range(m)]
		for x in range(m):
			matrix[x][0] = 1
		for y in range(n):
			matrix[0][y] = 1
		for i in range(1, m):
			for j in range(1, n):
				matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]
		mod = 10 ** 9 + 7
		return matrix[m - 1][n - 1] % mod


class Solution:

	def numberOfPaths(self, m, n):
		mod = 10 ** 9 + 7
		dp = [1] * n
		prev = 1
		for i in range(1, m):
			for j in range(n):
				if j == 0:
					dp[j] = 1
					prev = 1
				else:
					dp[j] = dp[j] + prev
					prev = dp[j]
		return dp[-1] % mod


class Solution:

	def numberOfPaths(self, m, n):
		dp = [-1] * n
		for row in range(m - 1, -1, -1):
			res = [-1] * n
			for col in range(n - 1, -1, -1):
				if row == m - 1 and col == n - 1:
					res[n - 1] = 1
					continue
				right = down = 0
				if col < n - 1:
					right = res[col + 1]
				if row < m - 1:
					down = dp[col]
				res[col] = (right + down) % 1000000007
			dp = res
		return dp[0]


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[-1 for _ in range(n)] for _ in range(m)]
		dp[m - 1][n - 1] = 1
		for row in range(m - 1, -1, -1):
			for col in range(n - 1, -1, -1):
				if row == m - 1 and col == n - 1:
					continue
				right = down = 0
				if col < n - 1:
					right = dp[row][col + 1]
				if row < m - 1:
					down = dp[row + 1][col]
				dp[row][col] = (right + down) % 1000000007
		return dp[0][0]

	def process(self, row, col, m, n, dp):
		if row >= m or col >= n:
			return 0
		if row == m - 1 and col == n - 1:
			return 1
		if dp[row][col] != -1:
			return dp[row][col]
		right = self.process(row, col + 1, m, n, dp)
		down = self.process(row + 1, col, m, n, dp)
		dp[row][col] = (right + down) % 1000000007
		return dp[row][col]


class Solution:

	def numberOfPaths(self, m, n):
		dp = [1] * m
		for i in range(n - 2, -1, -1):
			newRow = [1] * m
			for j in range(m - 2, -1, -1):
				newRow[j] = (dp[j] + newRow[j + 1]) % 1000000007
			dp = newRow
		return dp[0] % 1000000007


import math
import numpy as np

class Solution:

	def numberOfPaths(self, m, n):
		options = np.ones((m, n), dtype=int)
		for i in range(1, m):
			for j in range(1, n):
				options[i, j] = (options[i - 1, j] + options[i, j - 1]) % (1000000000.0 + 7)
		return int(options[m - 1, n - 1] % (10000000000.0 + 7))


class Solution:

	def numberOfPaths(self, n, m):
		count = [[0 for x in range(m)] for y in range(n)]
		for i in range(n):
			count[i][0] = 1
		for j in range(m):
			count[0][j] = 1
		for i in range(1, n):
			for j in range(1, m):
				count[i][j] = (count[i - 1][j] + count[i][j - 1]) % 1000000007
		return count[n - 1][m - 1]


class Solution:

	def numberOfPaths(self, m, n):
		prev = [1] * m
		for i in range(1, n):
			cur = [0] * m
			cur[0] = 1
			for j in range(1, m):
				cur[j] = prev[j] + cur[j - 1]
			prev = cur
		return prev[-1] % int(1000000000.0 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		x = []
		for i in range(m):
			x.append([0 for i in range(n)])
		for i in range(n):
			x[m - 1][i] = 1
		for i in range(m):
			x[i][n - 1] = 1
		for i in range(m - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				x[i][j] += x[i + 1][j]
				x[i][j] += x[i][j + 1]
		return x[0][0] % (1000000000 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		map = {}

		def solve(m, n):
			if m == 1:
				return 1
			if n == 1:
				return 1
			if (m - 1, n) not in map:
				r = solve(m - 1, n)
				map[m - 1, n] = r
			else:
				r = map[m - 1, n]
			if (m, n - 1) not in map:
				d = solve(m, n - 1)
				map[m, n - 1] = d
			else:
				d = map[m, n - 1]
			return (r + d) % (10 ** 9 + 7)
		return solve(m, n) % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, a, b):
		dp = [[-1 for _ in range(b)] for k in range(a)]

		def f(i, j):
			if i < 0 or j < 0:
				return 0
			if i == 0 and j == 0:
				return 1
			if dp[i][j] != -1:
				return dp[i][j]
			o = f(i - 1, j)
			t = f(i, j - 1)
			dp[i][j] = int((o + t) % (1000000000.0 + 7))
			return dp[i][j]
		return f(a - 1, b - 1)


mod = 10 ** 9 + 7
dp = [[0 for j in range(101)] for i in range(101)]
for i in range(101):
	for j in range(101):
		if i == 0 and j == 0:
			dp[i][j] = 1
		if i > 0:
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod
		if j > 0:
			dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod

class Solution:

	def numberOfPaths(self, m, n):
		return dp[m - 1][n - 1]


class Solution:

	def numberOfPaths(self, m, n):
		memo = [[-1] * (n + 1) for _ in range(m + 1)]
		mod = 10 ** 9 + 7

		def path(curx, cury):
			if curx == m - 1 and cury == n - 1:
				return 1
			if curx >= m or cury >= n:
				return 0
			if memo[curx][cury] != -1:
				return memo[curx][cury]
			(down, right) = (path(curx + 1, cury), path(curx, cury + 1))
			memo[curx][cury] = (down + right) % mod
			return memo[curx][cury]
		return path(0, 0)


class Solution:

	def numberOfPaths(self, r, c):
		grid = [[0] * c] * r
		for i in range(r):
			for j in range(c):
				if i == 0 or j == 0:
					grid[i][j] = 1
				else:
					grid[i][j] = (grid[i - 1][j] + grid[i][j - 1]) % 1000000007
		return grid[r - 1][c - 1]


class Solution:

	def numberOfPaths(self, a, b):
		n = a - 1 + (b - 1)
		r = a - 1
		fact = [0] * (n + 1)
		fact[0] = 1
		for i in range(1, n + 1):
			fact[i] = fact[i - 1] * i
		return fact[n] // (fact[r] * fact[n - r]) % 1000000007


class Solution:

	def numberOfPaths(self, a, b):
		grid = [[0] * b] * a
		for i in range(a):
			for j in range(b):
				if i == 0 or j == 0:
					grid[i][j] = 1
				else:
					grid[i][j] = (grid[i - 1][j] + grid[i][j - 1]) % 1000000007
		return grid[a - 1][b - 1]


class Solution:

	def solve(self, i, j, m, n, dp):
		if i == m - 1:
			return 1
		if j == n - 1:
			return 1
		if dp[i + 1][j] != -1:
			a = dp[i + 1][j]
		else:
			dp[i + 1][j] = self.solve(i + 1, j, m, n, dp)
			a = dp[i + 1][j]
		if dp[i][j + 1] != -1:
			b = dp[i][j + 1]
		else:
			dp[i][j + 1] = self.solve(i, j + 1, m, n, dp)
			b = dp[i][j + 1]
		return a + b

	def numberOfPaths(self, m, n):
		dp = [[-1] * n for i in range(m)]
		ans = self.solve(0, 0, m, n, dp)
		return ans % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, m, n):

		def haha(i, j, n, m):
			if (i, j) in dp:
				return dp[i, j]
			if i > n or j > m:
				return 0
			if i == n and j == m:
				return 1
			d = haha(i + 1, j, n, m)
			r = haha(i, j + 1, n, m)
			dp[i, j] = d + r
			return dp[i, j]
		dp = {}
		return haha(0, 0, n - 1, m - 1) % (10 ** 9 + 7)


class Solution:

	def numberOfPaths(self, m, n):
		dp = [[-1 for x in range(0, m + 1)] for j in range(0, n + 1)]

		def recur(m, n):
			if m == 1 or n == 1:
				dp[n][m] = 1
				return 1
			if dp[n][m] != -1:
				return dp[n][m]
			dp[n][m] = (recur(m - 1, n) + recur(m, n - 1)) % 1000000007
			return dp[n][m]
		recur(m, n)
		return dp[n][m]