Doubt in memoization

#1

Hii…
I am doing this question from leetcode.
740. Delete and Earn

I have used recursive approch along with hashing.
In my code…Here two paramater are changing one is index and other one is map which i am using.
This code is showing TLE.
But i am unable to find any approch to memoize it.
Please look at my code and tell me how could i memoize it.
This is my code…


Thanks

#2

hello @ashishnnnnn
pass your map by reference and then try

#3

Hii…
It is showing wrong answer now…


I think because the keys and value in map is also changing along with the index i.
I am not getting idea, how to memoize both.
Please see this.

#4

@ashishnnnnn
first u need to remove all duplicates from ur array (after storing their frequncies) .
then u need to sort the array after that it is very easy (sorting becuase then we only need to check for consective element) .
->
solve(n)=include nth element + [ solve(n-1) if value at n-1 is not num[n]-1 otherwise solve(n-2) ]
or
discard nth element solve(n-1)

whichever give max pick that one.

so a simple linear dp array is sufficient for memoisation

#5

Hii…
I got what you are recommending me to work upon.
I have done like that with recursion+memoization and it got accepted.
This is the solution


Thank you very Much :slight_smile: :slight_smile:

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.