Memory Limit Exceeded for top down approach with memoization


#1

Hi,

I am constantly getting “Memory Limit Exceeded” for my top-down approach with memoization.
I changed my int 2D array to a bool 2D array but I am still facing this problem. I am getting an ok for correctness, so I don’t think my solution is wrong.

A little help would be appreciated as I cannot come up with a better solution using less than O(n^2) space!

Thanks in advance!!


#2

Try to figure out in what direction you move in your 2d array, note that in order to calc arr[i][j] you will need only the previous row/column


#3

You need to use boolean array, you might be using int array


#4

I was getting memory exceeded limit error too. I don’t how this works but i changed the initialization of strings in my recursive function from string A to const string &A and it got submitted.


#5

Top-down approach is giving memory limit exceeded error because the length of the input string can be up to 9e4. And I think most of the online compilers provide array space up to 1e5. In Top-down we will need to use recursive stack space as well, so you can imagine how much space we are using combining these two. So, go for the bottom-up approach as you will require array space only.

The same was happening for me but bottom-up worked out for me.