Welcome back.
So this is the code that we had previously written for writing the recursive solution for the LCS question.
Now let's go ahead and memorize this.
And you will see that.
To achieve that we would just need to add a few lines of code.
To start with, let's create a 2D dp array which will have n rows and n columns okay.
So let's do that.
Length in okay.
So it will have n rows and we need it to have m columns.
So let's do that.
And what we are doing is we are going to fill every cell in this 2D dp array with the value minus one.
And you will have noticed that this is something pretty common across problems where we memoize a solution.
Again, this is useful because we can check whether we have previously computed something or not using
this.
Okay, now after creating the DP array, let's go ahead and modify the helper function slightly.
So after the base case, before we go ahead and compute the recursive case, we will check whether we
had previously computed and stored this particular index one index two combination in the DP array or
not.
Okay, so we'll say if dp at index one index two not equal to minus one okay.
So if it's not equal to minus one it means that we have previously computed and stored this value in
the DP array.
And that's why it's not minus one.
Because over here we had filled every cell in the DP array with the value minus one okay.
So if this is not equal to minus one then we will just return dp at index one.
Index two okay.
Now if this is not the case then we proceed with the recursive case.
So over here if text one at index one is equal to text two at index two, then we will not return this,
but rather we will store this in dp at index one index two.
So over here and say dp at index one, index two is equal to one plus whatever we get back from this
recursive call okay.
Now if this is not the case.
So let's write an else statement over here.
So if this is not the case then we'll say dp at index one.
Index two is equal to whatever we get over here.
So let me copy this.
Let me cut and copy this.
And I'm pasting it over here okay.
And after that over here when we come over here we'll just return DP at index one.
Index two.
And that's it okay.
So notice that we were able to memorize the recursive approach by just adding a few lines of code.
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 working.
It's passing all the test cases.