Let's first discuss how can we identify that the Liz question is a DP question.
And then let's proceed with the approach of solving this question.
So for identifying the Liz question as a DP question, notice that we have two hints.
First, we are asked an optimal solution because we are asked to find the longest increasing subsequence
length.
So longest over here indicates that we are trying to find an optimal solution.
And we had previously discussed that.
This is one of the hints that can be used to identify questions that can be solved with dynamic programming.
The second hint over here is that we have choices at hand.
So for example, to form a subsequence, we can either include an element or exclude an element from
the array which is given to us.
So we have choices.
So this indicates that we could solve this with recursion.
And we also see that we have two branches like.
Let's say we start at a particular index and we exclude and we include and then we go to the next index.
So again we have the options of excluding or including.
And we had previously seen that especially when you have choices and when you have a tree that looks
like this where you have multiple branches, there is a high probability for having overlapping subproblems.
And hence probably the question could be solved using dynamic programming.
Now let's get started with how to approach solving this question.
We have understood that we want to solve this with dynamic programming.
But remember, it's very difficult to start with the bottom up or tabulation approach directly.
Don't do that.
If it's a question that you're trying to solve for the first time, or especially if the variant that
you're trying is not something that you've encountered previously.
So if that is the case, the best approach for solving DP questions is first to write the recursive
solution, then come up with the memoization approach, and then finally come up with the bottom up
or tabulation approach.
So this is the methodology that we will use over here as well.
And again the advantage is that if you solve DP questions in this manner, you will be able to solve
even new questions or questions that you have not previously encountered successfully.
So let's get started.
First with the recursion approach.
Now, in the recursive approach, we'll have to think of what the base case is and what the recursive
case is.
Now remember, recursive solutions can be written either going from zero to n or n to zero.
Over here, let's take the approach where we are going from zero to n.
Now to discuss the recursive approach, let's take an example.
Let's say the array which is given to us is one, two, three.
Now first let's come up with the choice diagram to identify the recursive case.
And again this is helpful because we have choices at hand.
And it's always helpful to visualize the choices that we have using a choice diagram.
Now remember whenever we consider including or excluding a particular element, it's important to know
which element was previously included in the subsequence.
And for that we need to know the index of the previously included element.
And this is needed because the question says that we need to form a strictly increasing subsequence.
So let's say previously we had included an element two.
Then if this is the last included element, any further element that's going to be included in this
subsequence has to be greater than this value over here.
So that's why we need to remember the previously included elements index.
So this is something that we need to keep in mind now to understand this in a good manner.
Let's take an example.
So we have the example 123 over here.
And let's say we are considering to include the element two.
All right.
So let's say this is the current element.
And to know whether we can include this in the subsequence that we are building, we need to know the
previously included element.
And for the sake of this example, let's say that one was previously included in the subsequence that
we are building now.
Over here we see that two is greater than one, and therefore we know that we can include two in the
subsequence that we are considering.
And when we include two in the subsequence, notice that the length of the subsequence increases by
one.
So this is something that we will keep in mind to come up with the recursive solution.
Now remember, for each element in the array which is given to us, we have two possibilities.
The first possibility is to include it in a subsequence, and the second possibility is to exclude it.
Now we can always exclude an element from a subsequence.
That's not a problem.
But to include an element in a subsequence, the element at hand has to be greater than the last included
element in the subsequence.
So we just need to go over all the elements in the array which is given to us, and then we have these
two choices for each element that is either included or excluded.
Now if we just go through all the elements of the subsequence which is given to us, and if we just
do, these two choices include and exclude and proceed to the next available index, we would get all
the possible subsequences.
Now, if we get all the possible subsequences, we can find the length of the longest increasing subsequence
by just taking the maximum value.
If we ensure that every subsequence formed follows the rule of being strictly increasing.
Now, before we proceed and do a dry run of the approach that we are going to implement for the recursive
solution, let's just take a moment to build our intuition to understand whether this is true.
Is it really true that if we just go through every element in the array which is given to us, and if
we do these two choices, that is, include the element and exclude the element, is it really true
that we would get all the possible subsequences?
Now for this we have this example over here 123.
Now initially we are at the element.
At index zero we exclude.
We get an empty array.
We include one.
We get an array with one we proceed to the next element.
Now we exclude.
We get again an empty array.
We include two.
We get two over here and over here.
When we exclude we get one.
And when we include two, we get one and two.
And then finally we do the same thing with three.
And notice that these are the subsequences that we are getting.
And this in fact has given us a list of all the possible subsequences that can be formed from this array
over here.
Now, when we do this, we will not blindly include every element as we've discussed.
We will have the check that the element at hand has to be greater than the previously included element.
But over here, we were just building the intuition that just by including and excluding elements and
by going over all the elements in the array which is given to us, we can in fact get all the possible
subsequences.
Now we have discussed the choice diagram and we have built an intuition.
So we're just going to exclude and include elements and go over all the elements in the array which
is given to us.
We've also discussed that before.
We include an element.
We will check whether the value at hand is greater than the previously included element.
So more of that coming soon in the next video.
But over here, let's take a moment to think about the base case as well for this recursive solution.
Now we have decided in this case to go from zero to n, but we could have gone from N to zero as well.
For the sake of this discussion, let's continue with the zero to n approach.
So initially we start with the element at index zero.
Then we proceed to the element at index one.
And this keeps happening till we reach the last index over here.
So if the length of this array over here is equal to n, then if we reach the value for the pointer
which is used to iterate over all the valid indices, if that value reaches a value greater than n minus
one, we would have encountered our first invalid input.
Now again taking a moment over here, this n over here, let's say it's the length of the input array.
And in general when we were saying zero to n, this n indicated the last valid index.
So in this case this would be zero to n minus one because n minus one is the last valid index.
So if the iterator gets a value which is greater than n minus one, we have hit our first invalid input.
And in this case we can just return zero because if there are no valid elements, we cannot form any
increasing subsequence and the length of a non existent subsequence is just zero.
So that's why we can return zero over here.
So we have built a first level understanding for implementing the recursive solution.
For the Alice question, we have discussed what the choice diagram would be, as well as what the base
condition is.
We have also developed an intuition why the choice diagram actually works, and why by just going over
the elements of the array and either excluding or including elements, we will be able to get all the
possible subsequences.
And we have also discussed what conditions are to be checked before we decide to include an element
into a subsequence.
Now in the next video, let's go ahead and draw the recursion tree of this approach.
And once we are done with this, we will have a thorough understanding and we will be able to easily
implement the code of this solution.