Hello all and welcome back.
So in this video let us continue our discussion on dynamic programming.
And now let us understand another way through which we can solve questions using dynamic programming.
Now in the last couple of videos, I am pretty sure that you must have gotten a basic idea on what exactly
dynamic programming is, and how it helps us to solve questions in an optimized manner.
Along with that, you should also understand the basic idea, the intuition behind dynamic programming.
And that is exactly the same as we discussed in the first video.
That is, if we have overlapping subproblems, basically subproblems which are getting solved again
and again, we should save their solution once we have solved them.
Okay, so that's the basic idea behind that.
Pretty sure you must have also written the code yourself.
Moving forward, I will be giving you many questions which you will be trying, and then a lot of fear
which you might have for dynamic programming will just be away.
Just one thing to please make sure is that try that your recursion overall approach, as well as the
concepts are a lot clear because for dynamic programming, recursion is required.
You cannot do DP without knowing recursion okay.
So in this video I want to talk another approach to solve the same question, or rather to solve dynamic
programming questions.
Right now it is normally known as dynamic programming approach.
The first one, which we learned was a memoization technique, right where we were adding memory to
our recursion.
Now, when we are given to find a Fibonacci number, how do we do it ourselves?
Like when if we don't have to use any particular, let's say, code or anything, let's see how exactly
do we solve that particular question?
So let's say you ask me what is the fifth Fibonacci number, right?
I will be writing down the first 211.
Then I will say that okay, I have these numbers.
Then let me add two here, because two is, which is what I get after adding two ones.
Right.
Then moving forward.
So let me draw it like this.
So it is a lot clearer.
Now I will write down three.
Now I can write down five.
And let's say this is overall 01234.
And if we needed to find the fifth number fifth Fibonacci number, that is going to be eight, right?
If you will pay attention, I have worked in this particular manner here.
Right.
As compared to our code, the recursion code which we wrote here, what we were doing, let's say we
wanted a particular number.
So for example
012345
for getting the fifth Fibonacci number I used to call directly on recursion.
I used to call directly with my function where I used to keep it Fibonacci of five, right?
Then after that, what we used to do once I get on five, I used to see for the last two numbers if
I have them or not.
Similarly, this used to see the last two numbers if it has or not.
Two used to see for one and zero and one.
Of course we used to have.
So there we can write down the base case.
Base case used to be one and one right.
So this is the overall your base case.
But I'm pretty sure that you must be able to see the difference.
The difference is that when we are solving using memoization or recursion, we are starting with our
answer.
We are starting with the top most value which we need.
Whereas when we have to ourselves solve it.
Or I should rather say that there is one more, very different way of solving this particular problem.
That is, if I start from bottom.
Okay, now the subproblems are the same again.
Getting the Fibonacci of two.
Fibonacci of three, Fibonacci of four.
All these are same.
You will be having the same subproblems.
But this time, instead of starting my overall approach from top, which I did in the right side where
I started with five, I am trying to build up my answer from the bottom.
Okay, so this approach is actually known as dynamic programming approach or the bottom up approach.
Okay.
So let me write that down.
The idea.
I hope it's clear it's known as bottom up.
And this particular approach is known as top down.
It is also known as memoization.
Okay.
And this one is known as Tabulation.
Tabulation.
Normally it is also called as pure DP, but I think tabulation is better to not confuse us.
But I hope you are able to get the basic idea in this.
Overall, what we are aiming to do.
We want to calculate the answer.
From bottom.
Okay.
So let's go down and we will see the code as well.
But first let us discuss few things.
What exactly will we be doing.
We started with when we wrote the recursion code for our problem right.
So we first write the recursion code.
Then after that what we did, we were using recursion again, but this time in line with the principle
of dynamic programming.
I added a memo array or memoization, in which we were solving the solution or storing the solution.
Storing sub problem.
Solution.
Now, given any particular DP question, write the best identifier.
If the question can be solved by a DP or not is actually.
If you see overlapping subproblems, write the same which we were able to see in your Fibonacci.
One thing more always, you have to make sure that you first write the recursion code.
Then you make the memo array okay, so as to do the memoization in that if you just add 4 or 5 lines
just to save your solution, you will be very good to change your whole DP whole recursive code into
a well optimized memoization or top down approach, right?
In the last approach, what we are expecting is that we need to get rid of recursion altogether.
So we want to just do a bottom up or tabulation approach.
Okay.
So here what we want.
No recursion.
Directly.
Solving or storing the solution.
And I hope you get the basic idea here as well.
When what we did when I asked you to calculate this yourself.
Right.
So we were not using any recursion or anything, right.
We were just using an storage.
You can call this as a list or something.
And using that we were able to get to our answer.
Right.
So nothing like recursion we were using.
Even if you ask a school, children would have never heard of recursion.
He can solve this question in this way.
Okay, so let's see everyone how we are going to write the code for this.
So let's say def Fibonacci.
And please make sure that you are understanding the basic idea.
My whole approach in explaining you like this is to make sure that intuitively the idea is clear.
Okay, great.
So this time what I'm going to do, I normally try or the way I used to keep their name is I use DP
okay.
So I normally use DP if overall one minute let me just do zero into n plus one.
So whenever I am writing this bottom up solution, I use the name as DP.
And for a memoization solution I use memo as an array name.
Just something to remember.
There is no hard and fast rule for that.
We use the diary in the last video, so as to make sure that you are able to understand that, but normally
going forward I will suggest to make sure that you are able to differentiate the approach you have followed.
Please make sure that you also fix a name.
Now what I will be doing everyone I will be calling this Fibonacci number with let's say five or N rather.
And I get my answer in this.
I'm just going to now print my answer.
Great, I can send this DPI as well.
That should be fine.
I think I'm just sending this DPI list.
I am initializing it with zero and n plus one.
Okay, great.
Now let me try to just solve this particular question again.
What exactly will we be doing here?
Okay, so pay attention.
If n is less than equal to one we can just return one.
But before returning I will try that.
I am saving this particular question okay.
So saving this particular answer.
So DPI of n equals one.
Let us try to understand this.
I had these when I started up right.
So let me just draw the DPA and let me help you visualize.
How are we going to fill this up in a bottom up manner?
So pay attention everyone.
This is let's say, our DPA.
Okay.
What I'm doing effectively this is the zero one, two, three, four, five and six okay.
So let's say we are talking about six.
I just want to make sure that you get the basic idea that how exactly is this happening for the first
two I know the answer right.
Again, you cannot tell me the second Fibonacci number if I don't give you the first two, something
which we have seen in recursion as well.
Right?
There are two base cases.
First time we use two base cases.
So effectively if you don't have two numbers, the last two numbers, you cannot tell me the second
number.
What is here?
Okay.
Similarly, if I ask you directly for four, you cannot tell me unless you have these two available
with us.
Right?
So we cannot say that.
Hey, this is the fourth Fibonacci number.
Before having these two numbers.
So the whole idea is that let us take a number and understand where the dependency lies for three.
I know the dependency lies on these two.
Okay.
So once we have understood this, then let us try to understand the constraints or the base case as
well.
Let me write that down.
Understand base case.
Understand base cases.
Okay.
So let us try to see this everyone.
How can we do that.
I know these men are my base cases.
Base case one and base case two.
I can directly go and fill this.
These in my array.
In my list.
So what can I do here, everyone?
Actually, we can get rid of this Instead, DP of zero equals one DP of one equals one.
Now these I am writing because I know the answer.
They are the base cases.
Now let me fill this particular list in a bottom up approach, starting from the bottom, filling each
and every thing which I can actually fill because I have the dependency.
For example, for two the dependency is these two numbers, and I have both of them.
So I can very well write my answer for two, which is going to be two here.
Now if we move forward for three again the dependency is on these two values.
I can just add them and fill them here.
And it's going to be three.
Right everyone.
So let me do that.
First we have to make sure of one thing as well.
We can actually not we can send this deep inside as well.
Should be fine if I am initializing it by zero, or the better case will be to make it proper code.
I think I should just define it here.
So zero into n plus one.
Okay.
Again.
This time I will not be using recursion.
My idea will be based on understanding of recursion.
So everywhere you will be filling up your base cases and then see that what all are the different subproblems
which you can solve.
What do I mean by subproblems here everyone.
If you see this three it's also a subproblem, right?
Fibonacci number which is on third position.
It's a subproblem of my answer.
Fibonacci on six position.
So let me do this thing.
Let us do six.
Great.
Now I can start my loop.
So for I in range two to n plus one.
So I have to make sure that I go till six.
N is six.
Thus I have to make sure that I add plus one there because it's a range function okay.
Now let us pay attention everyone.
What do you think?
DP of two should be.
Let us first write for DP of two.
DP of two should be equal to DP of one plus DP of zero.
In a similar manner, DP of three should be equal to DP of two plus DP of one.
DP of four.
Right.
So I hope you are able to understand this.
Let me just write that down as well.
DP of zero plus DP of one.
This will be one minute.
Right.
DP of two plus DP of one.
So all I am doing here is to make sure that any subproblem which I am able to solve, because all the
dependencies are clear, I am just solving that and filling up my table, filling up my DP array or
a list.
Okay, so this again I can write in a similar way as DP of three plus DP of two.
So this can be DP of four plus DP of five or DP of sorry three.
Similarly, the final one I can just directly say DP of five plus DP of four.
So if I am able to just solve and fill up my whole array, I can say that hey, this is going to be
my final answer, right everyone?
So I hope you're able to understand this.
If I just keep on filling this particular array or a list, then in the end, I can very comfortably
say that this is the final answer, something which we will now do, I hope you are able to understand
that how this particular depends on these two.
These two I need to have.
Without having them, I cannot actually solve or get any Fibonacci number.
Similarly, three depends on these two two and one.
Four depends on three and two.
So one by one I am trying to just make sure that I fill up all the things which I have a dependency
cleared.
For example, once I fill in two, I can get the three because these two are the numbers.
Then once I fill in three, I can get these right everyone.
So I hope you are able to understand that how just I am trying to codify or add code to the solution
or the approach which we were solving when we were getting the answer in our mind, or when we used
to get the answer.
So the idea is exactly the same.
This is the approach which we used to follow when someone asks you, you are not using recursion or
anything.
But again, to write these kind of solution, these pure DP solution or tabulation solution.
We have to understand recursion very well because as we move forward, the way this particular list
gets populated, it's going to be a lot dependent exactly on how well you understand the recursion code.
If you remember in the first video when we wrote the overall recursive or the memoization code where
we.
This was really pay attention everyone.
How exactly the list the diary gets populated everything is minus one initially.
First we are calling for n five.
This is the n five.
Let us move forward.
Now we are calling for n four.
This is n four.
Now for n three, then two, then one.
And we used to then fill up for these zero and one.
Right.
Because these are the base cases.
So just that I started from five here top down.
This time I'm starting from bottom up, so it's the direction I start from top and go down.
Start from bottom and go up.
This is just the difference which I am using to do my solution in a different way altogether.
Now the reason I am explaining you this with so much patience, with so many repetitive statements,
is I want to make sure that this sits in your mind always.
Okay.
Many students, they just understand it very quickly so they are not able to comprehend how exactly
the solution is getting built up.
And that's why I always make sure that in deep visualization is of most important okay.
Visualization is the most important thing which we can use.
Now in my solution I'm just filling it like this.
So same thing is going to happen here.
First you will see that we will have one here okay.
So pay attention everyone.
Initially zero and one will only get populated.
So see first we have one here.
Now we are going to call for zero and zero and one are filled.
Now two will get filled, then three, then four.
Okay, just that I am filling up in this way, but I called from the five.
So calling from the top and going to the bottom.
So this is how it was happening, right everyone, I hope you remember this.
We were just calling from the top.
All these calls are waiting in my DP solution.
I don't want to do that using these things.
How exactly it's happening.
I hope you get the idea.
So two is dependent on one and zero.
Three is dependent on two and one four is dependent on three and two.
So if I write this something like this I hope you get the idea.
DP of one is equals to dp of I minus one plus dp of I minus two.
The reason I took it as zero because I am adding it this time, right?
I am not checking if it is not minus one or something.
We can do that as well.
But again the idea is same if we have zero here.
Even if we make a mistake, this adding will not at least extrapolate our answer.
We can remove this.
All right.
Now, once we have run all of this, where do you think our answer will be?
Our answer should be somewhere on this because we want P of six.
Let's say in this example it will be here.
So six.
Right.
Let us try to run this everyone.
Now I am getting 13 which seems to be the right answer I guess.
So 0001234 okay, I just missed the fifth or sixth one.
Here, let me remove this.
Let us add five here.
And then of course based on our approach.
So we took one one as the zero and one number.
Right.
So many places you will see that the first Fibonacci number is one zeroth.
Fibonacci number is zero.
We have took to.
Both of them first.
So yes, we seem to get an answer, but something which I would like all of you to understand.
First, we are not using recursion here, and let me now try to help you visualize.
This function gets defined n equals six.
Answer Fibonacci.
The bottom up I'm calling this function okay.
But this function doesn't call other functions or is not using recursion.
Let us move forward.
Is n greater than or less than or equal to one?
No, so we cannot return one.
I am making a deep array c this particular array.
And now right in front of you you will see that how these values are getting filled up DP of zero I
know is one DP of one I know is one.
Next for I in range two to n plus one n is six.
So this loop is going to run for these values okay everyone.
So let me just draw this.
These are the values which I am interested in populating exactly the way we used to do it manually.
Exact same thing is going to happen.
We are just saying that hey, do this now.
Do this whole process in front of us.
So let us see how this gets fulfilled.
Everyone next I2I is two.
See this gets filled as 2I3 it gets filled as 3I4 as five, I five as eight and I six.
Finally as 13.
Once everything is done, I can come out of loop and you can see that DP of this n, which is six is
13.
And I get my answer as 13.
Okay.
So again, uh, honestly, if you ask me, you should be aware of both the approaches.
Just one downside is there in the memoization approach.
And that actually is let me write it in red here as we use recursion.
Extra call stack memory is required.
Whereas no such dependency or limitation is there in the bottom up approach.
Because we are not using recursion, we are just trying to fill in the answer based on the understanding
of our memoization code in memoization.
I also showed you that how do we start from five?
Finally, we fill these two the base cases only first, and then try to build up an answer.
But in bottom up we are starting from here only, and as we are not using recursion okay, it will not
have any such issues where call stack will get filled up.
Now you don't have to worry or you don't have to always chase the DP solution or the tabulation solution.
Everyone.
Because majorly in problems this code works fine the way you have to do recursion questions going forward
is in this particular manner.
First you will write the recursive code.
Then you will do the recursion plus memoization.
At this point you will make the table okay and try to fill it based on the exact step or exact order.
Your code is going to fill it.
And then finally we will do the bottom up or tabulation.
So we will always make sure that we write three codes for our problems in DP where it is dependent on
recursion.
Okay.
Great everyone.
So I hope this overall approach is now a lot clearer.
Let me just do one thing so that you understand.
Just let me keep all of this a little bit separate from the above.
So this is how you have to follow this and tabulation.
Approach.
Kate, everyone.
So with that, I hope this is clear.
Now in the upcoming videos I will be giving and discussing questions with you, which we have to make
sure that we do in all of these three approaches.
Please make sure again to see this video.
Again, for anyone learning deep for the first time.
It is a lot daunting initially, but believe me, the way I have, I am taking time.
I want each and every one of you to understand deep, completely in depth.
That is the reason I am making sure to spend so much time in solving these initial problems, so that
the fear of deep doesn't stay with you.
And as you move forward solving questions, you are able to take the full benefit of all your knowledge
and write deep code very easily.
Okay, so great everyone.
Now let's meet in the next video and we will be solving more and more questions, because that is the
best way to hone your skills.
The theory is not there, it's just a way of solving the question.
Just like recursion.
So we are going to do the same thing.