Welcome back.
In the previous video, we have seen how we can memorize the recursive approach and we were able to
achieve a much better time complexity, which was of the order of n squared as compared with the recursive
approach, which had a time complexity of the order of two to the power n.
Now let's discuss the bottom up or tabulation approach for solving the list question.
Now we can do this in two ways.
That is, using a 2D array or a 1D array.
So we will first discuss the approach where we are using a 2D array.
But also remember we can solve this question using a 1D array, because the state of the problem can
be represented with just one variable.
Or in other words, if we have an array, we can use just this one index over here to identify the answer
to a subproblem.
Or like for example, if we have three elements, then we have zero, one and two as the indices.
Now probably there is a way in which we can identify the alias for this subproblem.
Then we can identify the alias for this subproblem.
Using this subproblem.
And in a similar manner, we can use the solution to this subproblem for finding the alias where we
are considering this complete array.
So this indicates that probably we can just use a one dimensional DP array for solving this as well.
But more of that in a future video.
Now let's get started with the 2D version of the bottom up or tabulation approach for solving the alias
question.
Now to discuss this approach, let's take again an example where the array which is given to us is one,
two, three.
And over here n is three because we have three elements.
Now let me write the indices over here zero, one and two.
Now we have seen that in the recursive approach there were two parameters that had to be passed to every
call to the alias function, which were the current index and the previous index which was included
lastly in the subsequence at hand.
So the value we have discussed for the current index ranges from 0 to 2.
Or zero to n minus one, and the values for the previous index in this case would range from minus one
up to one, and minus one indicates that no value has been added to the subsequent so far, and it's
only going up to one because the previous index has to be lower than the current index, and the largest
value for the current index is two.
So that's why the previous index only goes up to one.
Now, as we've discussed in the memoization approach over here.
Also, we need to offset the values of the previous index over here by one so that we are able to represent
this in a 2D array.
Because over here we have a negative value.
And that's not conducive for representing this in a 2D DP array.
So let's offset these values by one.
So minus one becomes zero zero becomes one and one becomes two.
So over here now we can use this 2D table to come up with the bottom up or tabulation approach.
For the last question let's call this DP.
So we have DP over here which is a 2D array.
Now previous takes the values from -1 to 1.
But we have offset these values to zero one and two.
So that's these three indices over here.
So zero indicates prev is equal to minus one.
One indicates prev is equal to zero and two indicates prev is equal to one.
Now current takes the values from 0 to 2.
So we have zero one and two which are the values that current takes in this table.
Now what would a cell in this table indicate.
Let's try to think about that.
For example let's take this cell over here.
Now this cell over here gives the longest increasing subsequence that can include values at index two
or to the right of two.
That means it can include values starting at index two and to the right of it.
If there were more elements over here, we could include them as well if possible.
So the row value over here gives us the index of the first element that can be considered for this subproblem
to be included in the subsequence.
And then we can include all the elements to the right of it or greater than this index over here.
So that's what the row value in this DP table specifies.
And what about the column value.
So for this subproblem this subproblem over here the column value is one.
And we know that if this is one it indicates that prev is one minus one which is equal to zero.
So for this subproblem the value of prev is equal to zero, which indicates that any value to be included
in the subsequence, or in the longest increasing subsequence that is represented by this cell.
The value has to be greater than the value at index, prev or in this case index zero.
So over here at index zero, we have the value one.
So any value that is included in this subsequence represented by this cell has to be greater than this
value over here.
But again remember we cannot include this value only values starting at index two which is.
This index over here can be added to this subproblems subsequence.
We will soon see how to fill this table over here.
But because we have defined this subproblem, notice that the value that comes over here is going to
be equal to one, because we can only take elements starting over here, which is we just have three
to consider.
And we can include three to the subsequence because three is greater than one.
This one over here is this one which is the value at the previous index which is equal to zero.
So over here we would fill one.
But more of that later.
We have seen and understood the definition of the row and column for this 2D depee table.
Now before we have a dry run of filling this table, let's just play around with it a bit to solidify
our learning.
So this problem over here, can you tell me what it represents.
It represents that we can include values starting at index zero.
Because car is equal to zero and prev is equal to minus one, which indicates that as of now nothing
has been added to the subsequence.
So the values that we can include are one, two, three.
And there is no condition to be kept in mind when we start considering to include the first value over
here, because nothing has been added so far.
What about this cell over here?
This cell represents values starting at index one.
So we can only consider two.
And.
Three to be included to the subsequence, but prev is still minus one, so nothing has been added to
the subsequence.
So there is no problem in including this element because as of now nothing has been added.
In a similar manner, this cell over here considers only the element three and nothing has been added
to the subsequence.
Now, when it comes to this cell, notice that this over here is not meaningful because prev has to
be lower than the current value.
So we will not be filling this value.
And when it comes to this cell over here we can take elements starting at index one.
So over here also we have two comma three for consideration.
But the values have to be greater than the value at index zero.
And in this case that's equal to one.
So that's why we have greater than one over here.
What about this subproblem.
In this subproblem again we will only consider values starting at index two.
And that's just this one element three.
But the values whatever is to be included in a subsequence has to be greater than one, because that's
the value at this index over here.
All right, now, what about this cell over here again?
This cell has prev.
Greater than cur.
So this is not meaningful.
And we will not be filling it.
And over here also notice that prev is equal to one and cur is equal to one.
They can't be equal.
Prev has to be smaller than cur.
So this also will not be filled.
And then we come over here.
Over here cur is equal to two.
So we can consider elements starting at index two.
And because the array over here has just three elements.
So we only have one element over here.
And prev over here is equal to one.
So if we decide to include an element for this subproblem it has to have a value greater than two which
is the value at this index over here that's this prev which has a value two.
So whatever is to be included in this subproblems subsequence has to have a value greater than two.
So this is how we will fill this 2D dp array.
And then there is no cur equal to three.
Notice over here the last valid index is two.
So all of this has to be filled with zero right.
Because again when we wrote the recursive solution remember we had written that if cur is greater than
n minus one return zero.
So that's this zero over here.
Again remember in a previous video we had discussed writing the recursive solution will help us identify
the initial conditions for the tabulation approach.
And over here also we can just fill it with zero because there is no prev equal to three.
And again we will not be using this, but we can fill over here also the values zero.
So these are the initial conditions for the 2D depee table.
And once we are done filling this table can you tell me where will the answer to the problem be?
Or at which cell will the answer to the problem be located?
Yes, you are right, it's going to be over here.
So this cell over here will give us the answer.
Because again notice this subproblem means that nothing has been added so far.
And you can consider adding elements starting from index zero of the array which is given to us.
So notice that that is the original problem which was given to us.
So once we are able to fill this cell, we will get the answer to the problem at hand.
So first we will fill this cell.
Then we will fill this one.
And then in a similar manner we will fill these cells.
And finally we will come to this cell and find the answer to the question.
Now a quick side note.
Remember we did the same thing in recursion.
And that's why writing the recursive function before going for the tabulation approach or the bottom
up approach is quite helpful.
So notice over here in a previous slide we had said that las at curr and prev will return the longest
increasing subsequence starting at index curve to the right of it of the array which is given to us.
And that's what we've just now discussed about the row value for the 2D depee table.
Right.
So we have done the same thing when we were discussing recursion as well.
And over here notice that it's mentioned values have to be greater than the value at index equal to
prev.
And we had prev over here.
And that's the condition that we have discussed for the 2D table as well.
So we have prev in the column value.
So whenever we are trying to fill a particular cell we can start with values at this index over here
which is given over here.
And whatever value is to be included in the subsequence that will give the answer to this cell has to
have a value greater than the value at index prev in the array which is given to us.
So that's the same thing that we did when we discussed the recursive solution as well.