Welcome back.
We have discussed the recursive approach for solving the Liz question, and we have seen that the time
complexity for this was of the order of two to the power n.
Let's now see whether we can do better.
So we proceed to the memoization approach.
And remember memoization is just recursion plus storage.
So we would be able to easily memoize the recursive approach that we have previously written by just
adding a few lines of code.
So let's discuss this.
So over here we have the recursion tree that we had previously drawn for this problem, where the array
that's given to us is one, two, three.
Now how do we store things in a table in a way that we can avoid recomputing the same thing again and
again.
For example, notice over here the problem three comma two happened over here three times.
And you have two comma one twice.
Now with more complicated inputs, you will see that many subproblems are computed multiple times.
And by just storing these we can avoid recomputation.
And that's the memoization approach.
Now for these notice that we have hit the base case.
So we will not be storing this.
Now let's think about how to store useful solutions to subproblems so that whenever we encounter them
again in the future, we can just retrieve what we have stored and return it.
Now for the list question, we can either use a 2D table or a 1D table.
In this video, let's discuss the 2D approach and later when we are discussing tabulation, we will
discuss first the 2D approach, and then we will also discuss the 1D array approach for solving the
Liz question.
So over here let's go with the more intuitive 2D approach.
So I have a 2D array.
And notice that on the columns part I have the indices for storing the previous index.
And over here I have the rows indicating the current index that we are considering.
Because remember for every recursive call over here we had these two parameters, the current index
being considered and the previous index that was added to the subsequence at hand.
Now the current index goes from the first index till the last index, which is zero to n minus one,
and that's n values.
But the value for the previous index, as we have discussed, goes from minus one up to n minus two.
Minus one indicates that nothing has been added in the subsequence so far, and then it goes only up
to n minus two, because prev has to be less than curr, and the last value for curr is n minus one,
and therefore the value previous to this is going to be n minus two.
So the value for the previous index ranges from minus one to n minus two.
Now to store this in this 2D array we will offset these values by one.
And we will change -1 to 0 by adding one to it.
And n minus two becomes n minus one.
So over here also we have n values.
So let's write these indices over here.
So we have zero over here.
And then one and then two.
So that's zero to n minus one for this problem and for cur we have the values from zero to n minus one.
So zero, one and two.
So we will use this 2D table to store things that we compute.
And then when we need them again we will just retrieve from this 2D table in constant time and return
the value.
So that's the memoization approach.
Initially we will fill all these cells with minus one.
And then in each of these recursive calls after checking the base case, what we will do is we will
check whether the subproblem in this table over here is minus one.
If it's not minus one, if you see that, for example, when we have two comma one right.
So we would have stored it over here.
And then when we again come to two comma one over here, we will check whether this subproblem in the
2D table is minus one or not.
If you see that it's not minus one, then we would just return the value that we get from the 2D table.
Now where would two comma one be stored over here.
Let's take a quick look at that.
So car over here is equal to two.
So we have car equal to two and prev is equal to one.
So this is prev.
So when prev is equal to one.
Remember when we store it in the DP table we have to offset it by one.
So this becomes two.
So the solution to two comma one will be stored over here which is at two two.
Because remember again this two means prev is equal to one.
This one means prev is equal to zero.
And this zero means prev is equal to minus one, which indicates that nothing has been added in the
subsequence at hand.
So let's go ahead and see how we can implement this in code in the next video.