Welcome back.
Now let's get into the memoization approach for solving the list question.
And this is the recursive approach that we had previously written.
And you will see that we would just need to add a few lines of code to get this changed to the memoization
approach.
So let's get started.
First let's create a 2D dp array which will have n rows and n columns.
Okay.
So let's do that.
So we'll have n rows and we would need n plus one columns.
Okay.
And what we will do is we will fill every cell in this 2D dp array with the value minus one.
All right.
Now over here in the helper function after the base case before we go ahead and do these computations
over here, we will check whether we had previously computed this particular scenario and stored it
in our DP table.
So we'll say if dp at curr and prev plus one is not equal to minus one, then we will just return.
We don't need to again compute it, but we will just return dp at curr and prev plus one okay.
And again notice we have pref plus one over here.
And we have discussed why this is the case in the previous video.
But let me quickly review it.
Remember prev starts with minus one.
So that's why we always have to increase it by one so that the values for prev starts from zero and
then it goes up to n.
Okay.
So again the typical values for prev are from minus one up to n minus one.
And when you add one to it it changes to zero to n.
Okay.
So that's why we have everywhere where we are referring this we will have prev plus one.
Now let's continue.
Now if this is not the case then we would have to go ahead and compute the exclude value and the include
value.
Now let's say we have both of these.
And before we return this over here we will store it okay.
So let's do that.
So we can store it.
We can say dp at curr and prev plus one is equal to math dot max include and exclude okay.
The greater value between these two will be stored at DP at current prev plus one.
And then we can just return dp curr prev plus one.
All right.
So this is the memoization approach for solving this question.
And notice that we just had to add a few lines of code to change the recursive approach to the memoization
approach.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's passing all the test cases.