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!!

It seems like a factorial result. i.e. it'll get large and blow out the stack depth and memory quickly - you should have this issue with this problem. Have a look at answers to [this](https://stackoverflow.com/questions/12935194/permutations-between-two-lists-of-unequal-length) question. — jwal, Apr 27 '21 at 18:43

Woodford · Accepted Answer · 2021-04-27T18:47:08.397

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]

score 0 · Answer 2 · answered Apr 27 '21 at 19:01

It's a combination issue. You can calculate the answer instead of walking the whole (very large) tree.

from math import factorial

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)

def grid_calc(n,m):
    m -= 1
    num = factorial(m + n - 1)
    den = factorial(m) * factorial(n - 1)
    return num//den

for c in [grid_count, grid_calc]:
    print(c(12,12))

Timing is

%%timeit
grid_count(12,12)
# 364 ms ± 1.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
grid_calc(12,12)
# 503 ns ± 3.88 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

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

2 Answers2