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
Not sure why this was closed as a duplicate. The question in this post *can* be solved using the answers in the linked post but doesn't have to be, as demonstrated in the accepted answer here. Furthermore the questions themselves are not in any way duplicates of each other. — Woodford, Mar 02 '23 at 16:50

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