number of path grid problem Python, Memory Error and Recursion Error:

Question

so i tried to solve a simple grid problem and i solve like this :\

def grid_count (n,m):
    if m == 1 and n == 1:
        return 1
    if m == 0 or n == 0:
        return 0
    return grid_count(m-1,n) + grid_count(m,n-1)

and here N X M is rows and column of a grid but is not good for big input for eg. if i input--- > 18X18 for N and M it will give me a runtime error so i used dynamic approach and

dic ={}
def grid_count (n,m):
    # key  = str(n)+","+str(m)
    key = n*m
    if key in dic:
        return dic[key]
    if m == 1 and n == 1:
        dic[key] = 1
    if m == 0 or n == 0:
        dic[key] = 0
    dic[key] = grid_count(m-1,n) + grid_count(m,n-1)
    return dic[key]

if i do this i have 2 type of error

error_1 1 : RecursionError: maximum recursion depth exceeded while getting the str of an object

and i got the answer for this i.e. --- >

sys.setrecursionlimit(100**8)

but after that one more error is rising

error_2 2 : MemoryError: Stack overflow i dont know what i do know ,

any help!!

Answer 1

When you reach your base case you should just return the value instead of storing it in dic.:

    if m == 1 and n == 1:
        return 1
    if m == 0 or n == 0:
        return 0

Alternatively, you can initialize dic with your known values:

dic = {0: 0, 1: 1}
def grid_count (n,m):
    key = n*m
    if key in dic:
        return dic[key]
    dic[key] = grid_count(m-1,n) + grid_count(m,n-1)
    return dic[key]