Number of Unique Paths using Python3

 Number of Unique Paths

I solved this problem using recursion, on geeksforgeeks, we need to find the all the unique path to reach the bottom.

Question: url

Solution:

class Solution:

dct = {}

#Function to find total number of unique paths.

def count_path(self,a,b, i,j, count):

if i> a or j > b:

return 0

if i == a and j ==b:

return 1

if str(i)+"_"+str(j) in self.dct:

return self.dct[str(i)+"_"+str(j)]

#print(i,j)

count = count + self.count_path(a,b,i+1,j, count)
            + self.count_path(a,b,i,j+1, count)

self.dct[str(i)+"_"+str(j)] = count

return self.dct[str(i)+"_"+str(j)]

def NumberOfPaths(self,a, b):

#code here

self.dct = {}

return self.count_path(a-1,b-1,0,0,0)