In the previous videos, we have discussed the recursive approach for solving the LCS question, and
we have discussed that the time complexity of this approach is of the order of two to the power n plus
m, and the space complexity is of the order of N plus m.
Let's now discuss the memoization or top down approach for solving the LCS question, and we'll see
that we'll just have to add a few lines of code to achieve this.
So let's get started now for discussing the memoization approach.
Let's take an example.
So let's take the two strings which are given to us as a, b, c, d, e, f and a c, f.
Now we will need a 2D array to store things that we compute so that we don't compute it again and again.
So over here I have a 2D array.
Notice that I have a c f over here in the columns.
And I have a, b, c, d e f in the rows.
So this is one string and this is the other string.
Now you could change the position of the two strings and have ACF as rows and a, b, C, D, f as columns.
That does not matter.
Now let's write the indices over here.
So that's zero one and two.
And the indices over here are zero, one, two three, four and five.
Now in this table what does each cell represent.
For example what does this cell represent.
This cell represents the subproblem where we have a b, c as one string and a c as the other string.
So that's this subproblem over here.
Now what would be another subproblem.
Let's take this one for example.
So this would be the subproblem where we have a b c d e f as one string and we have a c as the other
string.
Or what would be this subproblem?
This subproblem has only a b as one string and a c f as the other string.
So that's what each cell in this 2D table represents.
Now let's go ahead and see how we can implement the memoization approach.
So the idea of the memoization approach is that it's still recursive in nature.
But whenever we are asked to find the answer to a subproblem, we will check whether we have already
computed it and stored it in this table.
If it's there, which can be found out by checking whether the value at that particular place in the
table is not minus one.
So if it's not minus one, we will just take that value and return it.
And that's just a constant time operation.
But if it's not there, we go ahead and compute the value and we store it and then return the value.
So we will compute every subproblem only one time.
So that's the core idea to memoize this.
So when we write the code for this, after checking the base case, before we go ahead and do the computation,
which is the recursive case, we would check whether the value at that particular position in the 2D
table is not minus one.
If it's not minus one, we just return the value.
So that's the memoization approach.
And again there's just a few tweaks to the recursive approach that we have just now discussed.
And we will again discuss this when we implement the code of this.
Now what would be the space and time complexity of this approach.
Now notice that the memoization approach is still recursive in nature.
So we will take up space on the recursive call stack.
And we also need space for this 2D array.
So that's why the space complexity is of the order of n into m plus the order of n plus m.
So this is for the table over here.
And this over here is for the space used on the recursive call stack.
Now, we have already discussed why this is of the order of n plus m when we discuss this for the recursive
approach.
So again, because n into m is greater than n plus m, we can say that the space complexity is of the
order of n into m.
Now what about the time complexity?
The time complexity will be of the order of n into M, because that's the upper bound, or the maximum
number of subproblems that we would want to compute.
And that's each of these cells over here.
Now typically we would not need all the subproblems.
But again we're just trying to find the upper bound.
And that's why the time complexity of this solution is of the order of n into m.