Hey there and welcome back.
So we have this problem over here.
And we have also discussed the 2d DP table that we will use for the bottom up or tabulation approach.
Now let's just go ahead and fill this table and have a dry run of the tabulation or bottom up approach
for solving the Liz question.
We have discussed that these cells over here represent the initial condition.
So let's just fill this up with zeros.
Now let's start filling this cell over here.
Now, this cell has a curve value of two and a prev value of two minus one, which is equal to one.
So cur is equal to two and prev is equal to one.
Now if this represents the array which is given to us, notice that index two is this value over here.
And that's what is given over here.
So we know that cur is equal to two.
Which means that we can consider elements starting at index two and going forward depending on the input
array.
Now we have to go ahead and calculate the exclude value and the include value for this particular subproblem.
And then the bigger value among these two will help us determine what value to fill over here.
So first let's discuss the exclude value that we can get.
Now excluding means we don't include this element.
And we consider only the remaining elements over here.
So that's the meaning of exclude right.
So we don't include this element.
And we consider the remaining elements now in the DP table.
What would that be.
So notice that in the DP table over here the exclude value would be dp at cur plus one.
Because when we do cur plus one we are moving over here.
And that means that we can only consider these elements.
So DP at cur plus one.
So that's the row value.
And then over here, because we have not included the value prev stays as it is.
So we have prev itself over here.
But then whenever we fill this to the DP table remember we discussed.
We have to offset this by one because prev is equal to one is column two in the DP table.
So that's why we have to do plus one.
So exclude is given by DP at cur plus one prev plus one.
So we have the exclude value over here.
So dp at cur plus one plus one is equal to this value over here which is zero itself.
And we have this value over here because we have filled the initial conditions in the DP table.
So this is the value of exclude.
Remember previously when we wrote the recursive approach for this question exclude was said to be list
of cur plus one prev.
And that's the same thing that we're doing over here.
Again notice the benefit or the advantage of first writing the recursive solution and then coming to
the bottom up or tabulation approach.
So this is the same thing.
Just we have plus one over here because we have to offset the value of prev while filling it to the
DP table.
So we have got exclude to be equal to DP at cur plus one prep plus one.
And that's in this case equal to zero.
Now let's go ahead and calculate the value for include.
So include is possible only if the value at index cur is greater than the value at index prev.
So over here prev is equal to one.
So the value at this index is equal to two and cur is equal to two.
And the value at index two is equal to three.
Notice that three is greater than two.
And therefore we are able to include.
So include is going to be equal to one plus.
And then you have to move to the next element in the input array.
So you have to do dp at cur plus one because you included the element at index cur.
And then we only consider elements to the right of Cur.
So that's why we have DP at cur plus one over here.
So we start with elements at index cur plus one.
And notice that prev also has changed.
Prev has to be set to cur because that's the latest element that was included to the subsequence.
And that's why we have cur over here.
And then we have plus one because we have to offset the value of prev before adding it to the DP table.
Notice prev one was added in column two.
So prev equal to cur will be added in column cur plus one.
And that's why we have plus one over here.
So include is going to equal to one plus dp at cur plus one cur plus one.
So we have discussed that we have cur over here because prev is equal to cur.
And then we have plus one over here because we have to offset the value by one.
Now in the table over here where is dp at cur plus one.
Cur plus one.
So over here cur was equal to two.
So cur plus one is equal to three.
So this is dp at three three which is this cell over here which has the value zero.
So include is equal to one plus zero which is equal to one.
So exclude is equal to zero and include is equal to one plus zero, which is one.
And the greater value between 0 and 1 is one.
And therefore we can fill the value one over here.
So we are done with this sub problem.
Now let's proceed.
We come over here where cr is equal to two and prev is equal to zero.
So again we have to calculate exclude and include.
Exclude will be DP at curve plus one which is three.
And you have pref plus one.
So zero plus one is one.
So this is the exclude value.
And include will be one plus DP at car plus one, which is three.
And again you have car plus one which is three.
And we are able to include because the value at index two, which is three, is greater than the value
at index zero, which is one.
So three is greater than one because of which we can include and therefore include is one plus dp at
three three.
So exclude which is DP at three one is this value over here which is zero.
And then dp at three three is also zero and one plus zero is one.
So this value is one and this is zero.
And the greater value between these two is equal to one.
And therefore we can fill the value one over here.
Now let's proceed to the next cell and we have car is equal to two and prev is equal to minus one.
And then again exclude is DPR Korea plus one plus one which is DPR three zero.
And we are able to include because nothing has been included so far.
So we can include and when we include include becomes one plus DPR three three.
Right.
Because car is two.
So car plus one is three.
And then over here also car is two.
And we have to do car plus one for the offset.
So this is also three.
So this value over here becomes one and dp at three zero is zero.
And the greater value between these two is one because of which we can fill one over here.
So we are done with these values.
Now let's come to the next cell.
Now the next cell to be filled is this cell over here.
We don't fill this cell because prev over here is equal to car.
But prev we know has to be less than car.
So we come to this cell over here and we have car is equal to one and prev is equal to zero.
And again you find exclude which is dp at two one and include which is one plus dp at two two.
And you are able to include because the value at index one, which is two is greater than the value
at index zero which is one.
So two is greater than one, because of which we can include.
And then we find exclude over here and include over here.
Now DP two one.
That's this value over here.
So exclude is one.
And then DP two two.
That's this value over here.
That's one.
So include is one plus one which is two.
And exclude is equal to one.
And the greater value between these two is two.
And that's why we fill two over here.
Now in a similar manner we come to the next cell and we fill two also over here.
And then we come over here.
When we come over here we have car is equal to zero and prev is equal to minus one and exclude is this
value over here which is two dp at.
Car plus one prev plus one.
That's exclude right.
So prev plus one is zero and car plus one is one.
So DP at one zero.
That's this value over here which is two.
So exclude is two and include.
Will be one plus DP at curve plus one and curve is zero.
So curve plus one is one.
And over here also you have one.
So DP at one comma one is this two.
And when you add one to it you get include to be equal to three.
Now the greater value exclude was three, include is exclude was two include is three.
Now the greater between these two is equal to three.
And that's how we fill three over here.
And that gives us the answer.
So the answer is equal to three which is the length of the longest increasing subsequence.
So this is the tabulation approach where we are using a 2D array for solving the Liz question.