The problem is to count all the possible paths from top left to bottom right of a MxN matrix with the constraints that from each cell you can either move to right or down.
Example 1:
Input:
M = 3 and N = 3
Output: 6
Explanation:
Let the given input 3*3 matrix is filled 
as such:
A B C
D E F
G H I
The possible paths which exists to reach 
'I' from 'A' following above conditions 
are as follows:ABCFI, ABEHI, ADGHI, ADEFI, 
ADEHI, ABEFI
 
Example 2:
Input:
M = 2 and N = 8
Output: 8
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numberOfPaths() which takes the integer M and integer N as input parameters and returns the number of paths..
Expected Time Complexity: O(m + n - 1))
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ M, N ≤ 10

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def numberOfPaths (self, n, m):
        # print(a)
        pass
        # code here


Solutions:
class Solution:

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


class Solution:

	def helper(self, i, j, n, m):
		if i == n - 1 and j == m - 1:
			return 1
		if i >= n or j >= m:
			return 0
		return self.helper(i, j + 1, n, m) + self.helper(i + 1, j, n, m)

	def numberOfPaths(self, n, m):
		return self.helper(0, 0, n, m)


class Solution:

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


class Solution:

	def numberOfPaths(self, n, m):
		pass
		mat = [[0 for j in range(n)] for i in range(m)]
		mat[0][0] = 1
		for i in range(m):
			for j in range(n):
				if j < n - 1:
					mat[i][j + 1] = mat[i][j + 1] + mat[i][j]
				if i < m - 1:
					mat[i + 1][j] = mat[i + 1][j] + mat[i][j]
		return mat[-1][-1]


class Solution:

	def numberOfPaths(self, n, m):
		return self.cntPaths(n, m, 0, 0)

	def cntPaths(self, n, m, i, j):
		if i == m - 1 or j == n - 1:
			return 1
		if i > m - 1 or j > n - 1:
			return 0
		return self.cntPaths(n, m, i + 1, j) + self.cntPaths(n, m, i, j + 1)


class Solution:

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


class Solution:

	def numberOfPaths(self, n, m):

		def count_num(i, j):
			if i == m - 1 or j == n - 1:
				return 1
			else:
				return count_num(i + 1, j) + count_num(i, j + 1)
		return count_num(0, 0)


class Solution:

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


class Solution:

	def numberOfPaths(self, n, m):

		def count(i, j, m, n):
			if i == m or j == n:
				return 0
			if i == m - 1 and j == n - 1:
				return 1
			dow = count(i + 1, j, m, n)
			rht = count(i, j + 1, m, n)
			return dow + rht
		return count(0, 0, n, m)


class Solution:

	def numberOfPaths(self, n, m):
		t = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if i == 0 or j == 0:
					t[i][j] = 1
				else:
					t[i][j] = t[i][j - 1] + t[i - 1][j]
		return t[-1][-1]


class Solution:

	def numberOfPaths(self, n, m):
		if m == 1 or n == 1:
			return 1
		path = [1 for _ in range(n)]
		prev = 1
		for row in range(1, m):
			for col in range(1, n):
				path[col] = path[col] + prev
				prev = path[col]
			prev = 1
		return path[n - 1]


class Solution:

	def numberOfPaths(self, n, m):
		pass
		paths = [[0 for _ in range(n)] for _ in range(m)]
		for row in range(m):
			for col in range(n):
				if row == 0 or col == 0:
					paths[row][col] = 1
				else:
					paths[row][col] = paths[row - 1][col] + paths[row][col - 1]
		return paths[m - 1][n - 1]


class Solution:

	def numberOfPaths(self, n, m):
		if m == 1 or n == 1:
			return 1
		else:
			return self.numberOfPaths(n - 1, m) + self.numberOfPaths(n, m - 1)


class Solution:

	def numberOfPaths(self, n, m):
		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[1][1] = 1
				else:
					l[i][j] = l[i - 1][j] + l[i][j - 1]
		return l[-1][-1]


class Solution:

	def numberOfPaths(self, n, m):
		pass
		if n == 1 or m == 1:
			return 1
		return self.numberOfPaths(m - 1, n) + self.numberOfPaths(m, n - 1)


class Solution:

	def numberOfPaths(self, n, m):
		if n == 1 and m == 1:
			return 1
		if n < 0 or m < 0:
			return 0
		return self.numberOfPaths(m - 1, n) + self.numberOfPaths(m, n - 1)


class Solution:

	def numberOfPaths(self, row, col):
		if row == 1 or col == 1:
			return 1
		if col < 1:
			return self.numberOfPaths(row - 1, col)
		if row < 1:
			return self.numberOfPaths(row, col - 1)
		return self.numberOfPaths(row, col - 1) + self.numberOfPaths(row - 1, col)


class Solution:

	def numberOfPaths(self, n, m):
		path = 1
		dp = [[1] * n for i in range(m)]
		for y in range(1, m):
			for x in range(1, n):
				dp[y][x] = dp[y - 1][x] + dp[y][x - 1]
		return dp[m - 1][n - 1]


class Solution:

	def numberOfPaths(self, n, m):
		path = 1
		for i in range(n, m + n - 1):
			path *= i
			path //= i - n + 1
		return path


class Solution:

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


class Solution:

	def numberOfPaths(self, n, m):
		rowL = n
		colL = m
		if rowL == 0 or colL == 0:
			return 0

		def helper(r, c, memo):
			if r == rowL - 1 and c == colL - 1:
				return 1
			if memo[r][c] != None:
				return memo[r][c]
			memo[r][c] = 0
			if r + 1 < rowL:
				memo[r][c] += helper(r + 1, c, memo)
			if c + 1 < colL:
				memo[r][c] += helper(r, c + 1, memo)
			return memo[r][c]
		memo = [[None for _ in range(colL)] for _ in range(rowL)]
		return helper(0, 0, memo)


class Solution:

	def numberOfPaths(self, n, m):
		count = 0

		def countPaths(i, j):
			nonlocal count
			if i >= n or j >= m:
				return
			if i == n - 1 and j == m - 1:
				count += 1
				return
			countPaths(i, j + 1)
			countPaths(i + 1, j)
		countPaths(0, 0)
		return count


class Solution:

	def numberOfPaths(self, n, m):

		def find(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]
			u = find(i - 1, j, dp)
			l = find(i, j - 1, dp)
			dp[i][j] = u + l
			return dp[i][j]
		dp = [[-1 for _ in range(m)] for _ in range(n)]
		c = find(n - 1, m - 1, dp)
		return c


class Solution:

	def numberOfPaths(self, n, m):

		def find(n, m):
			if n == 0 and m == 0:
				return 1
			if n < 0 or m < 0:
				return 0
			u = find(n - 1, m)
			l = find(n, m - 1)
			return u + l
		c = find(n - 1, m - 1)
		return c


class Solution:
	path_count = 0

	def path(self, n, m):
		if n == 0 and m == 0:
			self.path_count += 1
			return
		if n > 0:
			self.path(n - 1, m)
		if m > 0:
			self.path(n, m - 1)

	def numberOfPaths(self, n, m):
		self.path_count = 0
		self.path(n - 1, m - 1)
		return self.path_count


class Solution:

	def helper(self, m, n, memo):
		c = str(m) + ',' + str(n)
		if c in memo.keys():
			return memo[c]
		if m == 0 or n == 0:
			return 0
		if m == 1 and n == 1:
			return 1
		memo[c] = self.helper(m, n - 1, memo) + self.helper(m - 1, n, memo)
		return memo[c]

	def numberOfPaths(self, n, m):
		e = {}
		f = self.helper(m, n, e)
		return f


class Solution:

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

	def helper(self, n, m, i, j):
		if i == n - 1 and j == m - 1:
			return 1
		if i >= n or j >= m:
			return 0
		ans = self.helper(n, m, i + 1, j) + self.helper(n, m, i, j + 1)
		return ans

	def DPsolution(self, n, m, i, j, dp):
		if i == n - 1 and j == m - 1:
			return 1
		if i >= n or j >= m:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		dp[i][j] = self.helper(n, m, i + 1, j) + self.helper(n, m, i, j + 1)
		return dp[i][j]


class Solution:

	def numberOfPaths(self, n, m):

		def paths(i, j):
			if i == m - 1 or j == n - 1:
				return 1
			return paths(i + 1, j) + paths(i, j + 1)
		nOp = paths(0, 0)
		return nOp


class Solution:

	def numberOfPaths(self, n, m):
		vs = [1] * m
		for _ in range(1, n):
			for j in range(1, m):
				vs[j] += vs[j - 1]
		return vs[-1]


class Solution:

	def numberOfPaths(self, n, m):
		pass

		def path(i, j):
			if i == n - 1 or j == m - 1:
				return 1
			return path(i + 1, j) + path(i, j + 1)
		return path(0, 0)


class Solution:

	def numberOfPaths(self, n, m):
		a = []
		b = []
		for i in range(m):
			a = []
			for j in range(n):
				a.append(None)
			b.append(a)
		for i in range(0, m):
			for j in range(0, n):
				if i == 0 or j == 0:
					b[i][j] = 1
				else:
					b[i][j] = b[i - 1][j] + b[i][j - 1]
		return b[m - 1][n - 1]


import numpy as np

class Solution:

	def numberOfPaths(self, n, m):
		mat = np.empty((m, n))
		for i in range(m):
			mat[i][0] = 1
			for j in range(n):
				mat[0][j] = 1
		for i in range(1, m):
			for j in range(1, n):
				mat[i][j] = mat[i - 1][j] + mat[i][j - 1]
		return int(mat[m - 1][n - 1])
		pass


class Solution:

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


def pathsTo(i, j):
	if i == 0 and j == 0:
		return 1
	if i < 0 or j < 0:
		return 0
	left = pathsTo(i, j - 1)
	right = pathsTo(i - 1, j)
	return left + right

class Solution:

	def numberOfPaths(self, n, m):
		pass
		return pathsTo(m - 1, n - 1)


def pathsTo(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]
	left = pathsTo(i, j - 1, dp)
	right = pathsTo(i - 1, j, dp)
	dp[i][j] = left + right
	return left + right

class Solution:

	def numberOfPaths(self, n, m):
		pass
		dp = []
		for i in range(m):
			dp.append([-1] * n)
		return pathsTo(m - 1, n - 1, dp)


class Solution:

	def numberOfPaths(self, n, m):
		a = [[0 for _ in range(m)] for _ in range(n)]
		a[0][0] = 1
		for i in range(n):
			a[i][0] = 1
		for j in range(m):
			a[0][j] = 1
		for i in range(1, n):
			for j in range(1, m):
				a[i][j] = a[i - 1][j] + a[i][j - 1]
		return a[-1][-1]


class Solution:

	def fact(self, n):
		if n == 0 or n == 1:
			return 1
		digit = n
		while n > 1:
			digit = digit * (n - 1)
			n = n - 1
		return digit

	def numberOfPaths(self, n, m):
		m = m - 1
		n = n - 1
		summ = self.fact(m + n)
		d1 = self.fact(m)
		d2 = self.fact(n)
		ans = summ // (d1 * d2)
		return ans


class Solution:

	def numberOfPaths(self, n, m):
		total = n + m - 2

		def fact(n):
			ans = 1
			for i in range(2, n + 1):
				ans *= i
			return ans
		return fact(total) // (fact(n - 1) * fact(total - n + 1))


class Solution:

	def numberOfPaths(self, n, m):
		r = 1
		c = 1
		return self.solve(r, c, n, m)

	def solve(self, r, c, n, m):
		if r == n:
			return 1
		if c == m:
			return 1
		a = self.solve(r + 1, c, n, m)
		b = self.solve(r, c + 1, n, m)
		return a + b


class Solution:

	def numberOfPaths(self, n, m):

		def countPaths(n, m):
			if n == 1 or m == 1:
				return 1
			countleft = countPaths(n - 1, m)
			countright = countPaths(n, m - 1)
			return countleft + countright
		count = countPaths(n, m)
		return count


class Solution:

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

		def count_path(m, n):
			if m == 0 and n == 0:
				return 1
			if m < 0 or n < 0:
				return 0
			if self.dp[m][n] != -1:
				return self.dp[m][n]
			up = count_path(m - 1, n)
			l = count_path(m, n - 1)
			self.dp[m][n] = up + l
			return self.dp[m][n]
		return count_path(m - 1, n - 1)


class Solution:

	def numberOfPaths(self, n, m):
		if 1 in [n, m]:
			return 1
		return self.numberOfPaths(n - 1, m) + self.numberOfPaths(n, m - 1)


class Solution:

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

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


class Solution:

	def numberOfPaths(self, n, m):
		count = [0]
		self.dfs(count, m, n, 0, 0)
		return count[0]

	def dfs(self, count, ROW, COL, i, j):
		if i == ROW - 1 and j == COL - 1:
			count[0] += 1
			return
		r = [0, 1]
		c = [1, 0]
		length = len(r)
		for k in range(0, length):
			if self.isSafe(i + r[k], j + c[k], ROW, COL):
				self.dfs(count, ROW, COL, i + r[k], j + c[k])
		return

	def isSafe(self, r, c, ROW, COL):
		return r >= 0 and r < ROW and (c >= 0) and (c < COL)


class Solution:

	def numberOfPaths(self, c, r):
		dp = [1] * c
		for _ in range(1, r):
			for i in range(1, c):
				dp[i] += dp[i - 1]
		return dp[-1]


class Solution:

	def numberOfPaths(self, n, m):
		return self.numWays(0, 0, n, m)

	def numWays(self, rows, cols, n, m):
		if rows == n - 1 and cols == m - 1:
			return 1
		if rows >= n or cols >= m:
			return 0
		down = self.numWays(rows + 1, cols, n, m)
		right = self.numWays(rows, cols + 1, n, m)
		return down + right


class Solution:

	def numberOfPaths(self, n, m):
		pass
		d = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0:
					d[i][j] = 1
				else:
					d[i][j] = d[i - 1][j] + d[i][j - 1]
		return d[n - 1][m - 1]


class Solution:

	def numberOfPaths(self, n, m):
		dp = [[0] * m] * n
		for i in range(n):
			for j in range(m):
				if i == 0 and j == 0:
					dp[i][j] = 1
				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[n - 1][m - 1]


class Solution:

	def numberOfPaths(self, n, m):
		return self.solve(n, m, 0, 0, 0)

	def solve(self, n, m, i, j, count):
		if i == n - 1 and j == m - 1:
			return 1
		if 0 <= i < n and 0 <= j < m:
			count += self.solve(n, m, i + 1, j, count) + self.solve(n, m, i, j + 1, count)
		return count


class Solution:

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

		def path(i, j):
			if i == 1 and j == 1:
				return 1
			if i < 0 or j < 0:
				return 0
			if d.get((i, j)):
				return d[i, j]
			d[i, j] = path(i - 1, j) + path(i, j - 1)
			return d[i, j]
		return path(n, m)