Welcome back.
So far we have discussed the recursive approach and the memoization approach for solving the LCS question.
For the memoization approach, we have seen that the space and time complexity were of the order of
n into M, and this is still recursive in nature, so we do use space on the recursive call stack.
Notice that the time complexity has significantly improved.
It was over here of the order of two to the power n plus m, but over here the time complexity is of
the order of n into m.
Now the space complexity over here was better, but then the improvement in time complexity makes it
worth.
Now let's proceed and discuss the tabulation or bottom up approach, which is iterative in nature for
solving the LCS question.
For this.
Let's take an example.
Let's say the two strings which are given to us are p q, r s t and p r t.
Now the length of this string is five and the length of this string is equal to three.
Now if we add one to both over here we have six.
And over here we have four.
So for the bottom up or tabulation approach when we create a DP table we would need six rows and four
columns or vice versa.
All right.
So over here let's draw that.
So notice that we have p r t over here.
And we have an extra column over here which is empty in nature.
And we have rows for p q r s t.
But we have an extra row over here for an empty string.
Now in the memoization approach we did not need this.
But in the tabulation approach this is quite handy.
And it's a common practice to have something like this when we come up with the table for tabulation.
Now this is useful because we will use values from the previous row for identifying the value in a current
cell.
Let's say we want to identify the value that goes over here.
And for this we would use something from the previous row values and probably from a previous cell.
So that's why it's handy to have this, because we can just use this to fill out the initial conditions.
Now before that, let's quickly take a moment to understand what each cell represents.
Now for example, what is the subproblem represented by this cell over here?
Now the subproblem represented by this is p q having one string as p q and the other string as p r.
Because over here we just have characters till q.
So this becomes p q.
And over here we have characters till r.
So this string becomes p r.
So that's this subproblem over here.
Now let's go ahead and fill the initial conditions with zero.
So we have zero over here and we have zero over here.
Now you can think of it in two ways.
Remember we have discussed when we were discussing the recursive approach that when we were coming to
an index which was not part of these strings, then we would not be able to find any common characters,
and therefore the length of the common subsequence in that case would be just zero.
So that's why we have zero over here and zero over here.
Because think of it.
What does this row represent?
For example, what is this subproblem?
This subproblem is having an empty string as one string and PR as the other string.
So that's this subproblem over here.
And if one string is empty and the other string is PR, then the length of the common subsequence of
the longest common subsequence would be just zero.
So that's why this complete row can be filled with zero.
And in a similar manner, let's say this subproblem over here.
This means one string is empty and the other string is p q r.
Now if one is p q r and the other string is empty, there are no common characters, and therefore the
LCS for this subproblem is zero.
And that's why we can fill this complete row with zero.
So we have discussed the initial conditions over here we have everything zero.
And over here we have everything zero.
Now let's discuss how we can iterate over each cell that remains in this table to find the answer to
the problem at hand.
So we first start with this cell.
And remember from the implementation of the recursive approach, we have discussed when we drew the
choice diagram that there are two possibilities.
The two possibilities are one.
The two characters that we are comparing are equal, and the other possibility is that the characters
that we are comparing are not equal.
Now, if the characters that we are considering are equal, then previously what we discussed was we
would just do one plus a recursive call.
So the equivalent of it in this table would be depee at ij.
And let's say the indices I and j are used to iterate over these two strings.
And let's say we find that the characters at these two indices are equal.
Now if that is the case, then dp at ij would be equal to one plus dp at I minus one and j minus one.
Now what does this mean?
Let's for example, take this example over here where the subproblems are p q r and p r.
So we have p q r.
And we have PR.
Now we see that these two characters are equal.
All right.
So these two are equal.
Now, because these two are equal, we would just need to do one plus the solution to the sub problem
where the strings are p, q and p.
Now what is the place in the DP table where we have this sub problem which is p q and that's this p
q.
And P.
That's this P over here.
So the intersection is over here.
Which is nothing but d p I minus one and j minus one.
All right.
So that's why when the characters are found to be equal, depee at I j would just be one plus dp at
I minus one j minus one.
Now let's use this to fill the table over here because notice that p and p are equal.
So we have a case where the characters are equal.
So dp at I minus one j minus one is nothing but the diagonal element.
And we would just have to take this value and add one to it, because we have filled the initial conditions
over here.
Notice that we already have this value, and we can just add one to this value to get one.
And we can fill one over here.
Now let's proceed to the next cell.
So over here we see that we have P over here and we have R over here.
And these are not equal.
Now in the implementation the recursive implementation we have discussed in the choice diagram that
when the characters that we are comparing are not equal, we would have to do two recursive calls and
we would only increment one index at a time.
And then we would have to find the maximum between those two values.
So what would be the equivalent of it in the tabulation approach.
So we can say that we would have to find the maximum between depee at I minus one j and dp at I j minus
one.
Now why is that?
So let's take this example.
So we have PR over here and we just have P over here.
That's this subproblem over here.
So we have PR and we have p.
Now we see that these two characters are not equal.
Now because these two are not equal we will have to take two possibilities.
One possibility is where we take p and p.
We change this index to from R to p.
And the other possibility let me write that over here is taking R.
And nothing because we moved this index, we kept this there itself and we moved this index.
So again notice over here we had p r and p.
So these are the two indices that are being considered.
So in one case I'm moving this this index to over here.
So that's this case where I'm getting p and p.
And the other case I'm leaving this over here itself.
So I have it here itself.
And I'm moving this index to this place over here.
So I'm getting R and nothing.
So these are the two possibilities.
So I need to find the answer to these two subproblems.
And I need to take the maximum between these two.
So what are these two subproblems in the DP table.
So having r or p r this is R right.
When you have are you still have p r and you have nothing over here.
So p r and nothing.
So that's having p r over here and nothing over here.
Which is this over here.
Right.
So that's top.
Or you can think of it as DP at I minus one J.
And this one over here having p and p that's this p over here.
And this p over here.
That's this cell over here which is the left cell or DP at I j minus one.
So basically we have seen that when the two characters that we are comparing are not equal, we need
to find depee at I minus one j and dp at I j minus one.
And that's the top cell and the left cell.
And between these two we just need to find which is the greater value.
And that would be the value that we can fill in the cell at hand which is dp at ij.
So over here between 0 and 1 the maximum value or the greater value is one.
So we can fill over here one.
Again we proceed.
Now we are comparing p and t and notice that these are not equal.
Therefore we just need to take the maximum between the top value and the left value.
So between 0 and 1 the greater value is one.
So we fill one over here and we are done with this row.
Now we come over here.
And for this cell we have Q over here and P over here.
These are not equal.
So we take the maximum between 0 and 1 which is equal to one.
And in a similar manner over here we have q and r.
Again they are not equal.
So between 1 and 1 the maximum value is one itself.
So we fill one over here.
And then when we have q and we have t we again see these are not equal.
So the left value is one.
The top value is one.
So the maximum between 1 and 1 is one itself.
And we can fill one over here.
So we are done with this row as well.
And we come over here.
Now we have R and over here we have p.
These are not equal.
So between 0 and 1 the greater value is one.
So we can fill one over here.
Now we come to this cell.
So we have R again over here and over here also we have r.
Now these are equal.
So therefore we come to the diagonal value which is dp at I minus one j minus one.
And we add one to it.
So one plus one gives us two which is this value over here.
Then we come to the next cell we have r and we have t.
These are not equal.
So we take the left and the top cell.
So we have two and one.
And the maximum between these two is two.
So we can fill two over here.
We're done with this row.
Now, let's come to this cell.
Over here.
We have S and P.
They are not equal.
So between 0 and 1 the greater value is one.
So we fill that over here.
And again over here we are comparing s and r.
So they are not equal.
So between zero and between 1 and 2 two is the greater value.
So we fill two over here.
And then we come to the next cell.
So we have s and t.
They are not equal.
So between 2 and 2 again the maximum value is two itself which can be filled over here.
And we are done with this row.
And we come over here we have T and P.
They are not equal.
So between 0 and 1 the greater value is one.
We fill that over here.
And then we have t and r and they are not equal.
So between 1 and 2 the greater value is two.
So we fill that over here.
And then we have t and t.
Now t and t are equal.
So we take the diagonal value which is two.
And we add one to it to get three.
And we fill three over here.
And this is the answer to the problem at hand.
So the answer to this question is three.
Now why is this the answer.
Because notice that this cell represents the problem where you have p q r s t and p r t.
And that's the question which was given to us.
So that's why whatever we get over here is the answer to the problem.
And this is the tabulation approach or the bottom up approach which we can take to solve the LCS question.