Hi, everyone.
So in this video, we are going to understand this topic, DEPI, Danek programming, so many people
used to scared of danek programming, dippie, but what we will do, we will only be in the right way.
We will start from a very easy problem and we will slowly build up concept and then we will solve a
much harder problem.
So let's start with deep trouble understanding the deep.
Let us consider a very small example.
So let us consider the Fibonacci series.
So what is happening is it is so difficult, I can say is first to damselfish zero and one, and we're
finding out the next time you will at previous to so it will be one then you will like previous to find
out the current term.
And similarly this will go on.
So this will be three, then five, then eight, then 13 and so on.
So for finding out the current term, you will add previous to so this is zero Fibonacci number.
This is first Fibonacci number and so on.
So if you remember, we have already solved the question of finding the net Fibonacci number for finding
out the net number.
So let's see the.
So this is very simple code.
Now, let us try to understand this code so this Fibonacci function will find out the network number.
So this is the best case.
If the value of any zero, I will return zero zero zero and the first number is one.
So that's why I'm returning one.
Then for finding out the current Fibonacci number, it will be the addition of and minus one previous
one and minus two previous of previous.
So we are finding out and number what we will do, we will add previous to Fibonacci number so often
minus one end above and minus two.
Simple, but the problem with this code is basically this code is very, very slow.
This court is very, very slow.
So why this cold, this low?
Because if we'll see the time complexity, so let us analyze the time complexity.
So what is happening here and.
So I have and now let's go inside the function, so inside the function here, I'm doing constant work,
then this and function and function, it is calling on to their function and then it is adding those
two values.
So basically, this function is doing constant work.
This function is doing constant work.
It is just calling one and minus one and minus two.
So basically this is a function of function is calling on and minus one and it is calling on and minus
two.
Simple.
So similarly this and minus one will call on and minus two and minus three similarly and minus two will
call on and minus three and and minus four.
And this will go on.
OK, so this will go on now at this level, how many functions are there?
So when at this level, how many functions are there to add this level?
How many functions are there for?
Similarly, at the next level, I will have eight functions call.
And similarly, at the last level, they can be potentially due to the power and functions call.
So exactly.
They will not be told about any functions.
Call why?
Because of considerately.
So what will happen.
Three will call on two and one, then two will call on one and zero.
So one will return, zero will return.
And similarly when will return from here.
So what will happen to Destry if we'll see that carefully?
This is basically left biased where this is left biased because in the left hand side this is decreasing
by one and minus one then and minus two, then three to one.
So in the left hand side it is decreasing by one, but in the right hand side it is decreasing by two.
So and minus two then and minus four and so on.
Basically this tree is left biased.
So in the left hand side it will be much bigger and the right hand side it will be smaller.
Okay, so this fluidity, this, this will be the recursion.
So this is left biased.
But even if this is left biased, if you will add all these functions, call if you will add these functions,
call and you will do the calculation.
So total number of functions will be two to the power and so two to the right are the total number of
functions called.
And each function, each function is doing basically constant work.
It is just checking the base case and then it is using plus operator.
OK, so each function is doing.
Constant work, and these are the total number of functions gone.
So basically the time, complexity of our solution is due to the power and.
So for this cold.
Why this is slow, this is slow because the time complexities to do the power, and so this is very,
very bad, very, very bad.
So definitely we want something better.
So even if you want to find out.
So let me show you.
So even if you will try to find out 53 first.
Let us try to find out 23 number, so it is giving me output in one second.
Now, let us try to find out the 58 Fibonacci number so 50 and see it post so what it will do.
So it is doing the calculation.
It will take a lot of a lot of time.
So I am closing my output.
I am closing this screen because it's going to take a lot of lot of time.
So now you can understand our previous solution is to to the power in debt, so I'm not able to find
out the 58 number, if you will, run the code.
It is going to take a lot of a lot of time.
Now, how can we solve this problem?
So what is happening here?
Let me throw that gently and then we will try to understand what is the problem by the time complexities
to the power in.
OK, so let's see.
So you have known and will call on and minus one.
And minus two.
Then minister will call on previous to so it will call on and minus two and then minus three.
Then similarly, it will go on and ministry and similarly on the left hand side, so it will go on.
Now, what will happen when you will find out the answer of any ministry so it will return done when
ministers and ministers will answer to and minus one.
Now, what is happening here?
When and minister will get the answer from the left hand side, it will call on right inside and what
is right inside and ministry and if it will, Ticketfly.
We have already calculated and ministry, but here we are calculating again.
We will again calculate and ministry, we will do the same calculation again, so any ministry will
call on and minus two and minus four and and minus five.
So basically here we solve this problem.
We find out down to foreign ministry.
But here again, when we reach here, women, men and women will call on right.
And say we will again do the same calculation.
We will do the same work.
So basically, we are repeating our work similarly.
So when and minus and we are done the answer to then and we'll call on and minister and here if will
see carefully.
We have already sold our answer.
We have already done that calculation, Foreign Minister.
But here we are again doing the calculation.
Foreign Minister.
So the main problem by that time completely to the power end is basically we are repeating our work.
We are repeating ourselves.
We have Alladin and ministry, then vital and ministry again.
So what is the simple solution to avoid this problem?
So the obvious solution.
So this is very obvious solution and obvious solution is when you have done the work, basically store
it somewhere and then use it in the future.
So to store and use in future.
OK, so this is a very simple solution.
This is very obvious also, if you have done the calculation foreign ministry, then store the answer
foreign ministry.
So store it somewhere to store it somewhere, basically.
And then we are doing then we again, when you are doing the calculation, foreign ministry, so doing
instead of doing the calculation, you can take the answer from the store, the variable simple.
So basically store and use in future.
So this is a very simple solution.
So if you will store, if you will store.
So how many number of unique calls will be there?
So I'm talking about unique, a number of functions called so unique, a number of functions called
will be and only why because and we'll call and minutes and then I will call in and minus two.
And similarly Telvin and we will store the list all down to four one install down to four to restore
order and support and minus.
And we restore the answerphone and so basically total number of functions call will be in.
OK, addressed all calls will be repetition only, and since addressed all calls are repetition, we
can likely take the answer from the stored variables, from the stored answer.
Obviously, I know we can solve this question creatively also, but I want to improve our recursive
solution.
OK, so how can we improve our recursive solution?
So what we will do, we will make an error.
So I'm going to construct an array of size and plus one.
So that means my first index will be zero and my last index will be in simple.
Now what I will do, I will initialize this area with zeroes, so I will initialize this area with zeros
in this area is filled with zeros.
So what is my logic?
Logic is very simple.
We will store and you reduce the value.
As discussed above, I'm going to store and reuse our values, so what we will do so as soon is, for
example, as soon as you are able to find out what is a fifth one, I can remember what I will do.
I will go to the fifth value.
I will go to the fifth index and I will store the value.
So whenever in the future.
Whenever in the future you want to find out Fabianski of five, then you will go to the fifth index,
you will check is zero percent or there is some value.
So if there is some value present, that means I have already sold this question so I can directly use
this value.
Similarly, if in future you want to find Funaki of three.
So what you will do, you will go to index three and you will check oh zero percent there.
That means I have not done the calculation.
So let's do the calculation for above three.
And after doing the calculation, let's put the value at the third index.
So whenever in future you want to calculate Fabo three again, what you will do, you will go to index
three and you will check.
So is there any value present that is different from zero?
If there is a value which is different from zero, that means I have already sold Fabianski of three.
So that means I can take the value from here.
OK, so basically that is how we will be able to implement the solution.
We can store the values and then we will reuse our values.
So now let's write the code.
So let's create a function that will be integer, and the name of the function is when I get to see
what this when will take.
I have to find out and that number, and it will take area's input, so this area, the area that we
will initialized with all zeroes, again, the base case will be same if the value of any is zero or
the value of this one.
I will return when the biscuit is no difference.
Now, there will be one more condition, so if.
He often very often is not close to zero, that means you have already solved this problem for a network.
No.
So that means you can directly return without doing anything so you can return every often.
It is I really realized that if it grows and if the current value is not zero.
So that means I have already solved this problem and I have stored the answer.
So if this is not the case, that means we are doing the calculation for the first time.
So what will be my output?
What I have to do over finding out and not knocking them, but I have to call on and minus one and minus
two.
So I'm calling one and minus one and minus two.
Simple now, once you have calculated your output, what you have to do first, you restore your output.
So let us store my output first and then we will return the output and then we will return our output.
OK, so first story then did an output, so I'm storing the value for future use, so store.
For future use.
Simple, now let us discuss their time, complexity for this matter of two so you will see carefully.
But over time, complexity, so you have an.
So you have seen what will happen, so and will call on and minus one.
Then minus one and minus two.
Then in two will call one end ministry and this will go on finally to then one and then zero.
And then what will happen?
So when will it sunset at sunset and similarly to it and the answer similarly and ministry will return
its answer.
OK, so now when you reach and minus two, what will happen and minus two will call on and minus four
and and minus four is already calculated and minus four.
We have already started.
If you see I have an A minus four here so.
And a minus what.
We have already calculated the value and we are able to restore the value.
So this will be you will call here and my network will directly return the answer, because we have
stored the values for nd minus for then and minus two will return.
The answer to one, minus one and minus one will call on right inside.
This will be and minus three.
And directly and ministry, we will return the answer, so we have already stored the value, we have
already done the calculation and we have stored the value.
So so minus ministry will directly return the value it will not call on and minus four and then minus
five, it will directly return the value.
So minus on the value to N now N will call on and minus twenty eight inside and, and minus two will
directly return the answer because we have already calculated the value and we will restore the value
so it will directly return the value.
So how many functions are there.
So we will see carefully.
So there are total end calls in the left hand side and is calling on in Minnesota that in my history
and my history and anyone so there and concentrate left inside and each function is calling on the right
hand side once everyone will call them right inside once and they will likely return the answer.
So in total, there will be N and each function will go on right hand side so and listen.
So there will be total.
So these are the total number of calls and if you will see the function.
So we are doing constant work.
So this is we are doing checking.
Then again, we are doing some checks.
Then we are finding out the output.
So this is constant work.
We are just using blitz operator agame, constant work and then we are returning our output.
So basically, each function is doing constant work, each function is doing constant work, and there
are basically two to three hour angles.
So that time complexity will be bigger off and.
This is the time complexity, so let's see first, our time complexity was due to the power end, but
now our time complexities big off and see how much we are improving and we are improving a lot.
So if we see this cushion, if you will see this in the perspective of Eddie, so let's take an example,
let's say the value of and is it.
So what is happening?
We are constructing an area of nine size and plus one size.
So the first index is zero and the last index is eight.
So what will happen?
Eight will call on seven to find out the answer.
Seven will call on six.
Six will call on five.
And similarly, this call will go on.
So this is, let's say two, then I have one.
So two will call on one and two will call on zero.
And they both will return the answer.
So finally, two will be filled.
So after filling out the two, what will happen?
Three will be filled, then four will be filled, then five, then six, then seven and then eight.
And then I will return.
I will return this value.
OK, so how this ad is getting filled.
So first I'm going in this direction, new direction, and then I am feeling this very.
This way, so basically we are traversing the area two times, first we are going in the left hand side
and then we are when we are going in the right hand side, we are filling the area.
We are filling this area.
So this area was initialized with Xeros initially.
This area was in initialized with zeroes.
So first when the left hand side and then we will go from left to right inside this area will get filled.
Now if we will see carefully, if you will observe carefully one obvious improvement, what we can do.
So instead of going first in the left hand side, then the right hand side, we can directly go right
hand side, OK, we can directly.
So what we can do, we can directly, we can fill this area.
What we will do.
You take an area, you know that at a and these two values are fixed.
So I can instead of going instead of using this approach first go left and then go right, what can
I do?
I can actually fill this area in this way.
I can iteratively fill this area.
OK, I can I totally disagree, because if you had previous to you will get to her, then you will at
previous two, so you will get three here, you will add the previous two, you will get five here and
so on.
So we can actually we can agree to disagree.
So let's write the code for this one.
So I will be in for about three.
OK, so what it will do, it will take the well often it will not take in input, OK, because it will
construct better inside the function.
We will construct better inside the function.
So let us create dynamic at because the value of this variable so new it and we are creating variable
sized area.
So you should create variable size daily.
Using dynamic education, I want to create size and plus one and plus one.
Now, the first two values are fixed 32.
I have zero.
First of talking numbers are fixed.
So at one, I have one.
Now I'd have to do I will fill this area from left to right addictively.
So I have to start feeling from index to I will go till index in and I placeless.
So what I have to do.
So if you want to find out I why this is edition of I mean, this one.
And I a minus to.
Simple and finally, what we can do, finally, we can return our output and our output is a matter
of and by doing this is wrong, why this is wrong?
Because you have created the error dynamically.
So before it ends in the area, what will do?
We will delete our area.
OK, we have to delete ourself.
We have allocated the memory.
Now we have to delete the memory ourself.
So let's free the memory.
So delete.
Dilatory, so I have to leave the area, but if you leave the area, how can you return the value?
So that means I have to store value first.
So let's first store the value.
So I'm starting Disvalue.
So after destroying the value in output variable, delete data and then return the output.
So this is the cold, so let's call on February.
So I'm calling the function and I will give and as input.
So now I'm calling both the functions, I'm calling for three function, so this one.
And then I'm calling other oil function.
OK, so let's see.
OK, so this is actually free of to.
The value of this 35.
So the value of N is basically 40 Norzai, so 50 gives the output instantaneously.
So this function is taking time.
Let's give a bigger value.
So let's give the value of N four to five C.
This addictively approach, it is giving me answer in just one second, whereas the second one, due
to the power and function, it is taking a lot of time.
OK.
So dysfunction is returning value instantaneously and dysfunction is taking time.
So let us also call this function of two.
So for calling the function of two, basically you have to construct Benetti, so let us create an eddy.
So I have to create an area of plus one size and I have to initialize this area with Zardoz.
And then let's call all the functions, so.
Let's call the function of two and and you have to pass, Eddie, also.
OK, so I'm calling for both three function to function and function.
So let's see, let's compare all this.
So let's give the value of N four to five so C these two are giving me.
So this is for both to end the system of two, OK.
So basically the answer is coming out to be different.
Very different.
So this is OK, OK over here instead of one that should be written, so let me correct it.
So instead of mind, this should be an OK society.
Well, guess what, one mistake, he had a train platform, so there should be it should be in.
So now let's run our program again.
So if I give the value of N four to five, so this is basically four of three and this is above two
and one will take a lot of time.
So let's not wait for.
When function.
So this is for one function, it is taking a lot of time, so if you will see it carefully.
The first method due to recursion, it takes two to the power, and so these are the total number of
calls.
In the second matter, the total number of calls was to win, so the time complexity was big often why
it is to win, because first we will go in the left hand side, then we will go in the right hand side
and the size of the arrays and so unpleasant to calls in the third approach, the A.N. approach, what
we are doing, we are just trading in one direction.
So that's where the time complexity is big often.
So what we are using here, so basically.
So in the third approach, what we are using, I am creating our data to store our results so it will
see carefully, we can also solve this question with the help of three variables, with the help of
three variables.
And we do not need this any white variables because it will say carefully selected for filling out any
entry.
Suppose you want to fill this entry.
What do you want?
You want the previous entry and previous of previous entry.
So what will do?
I will take one variable for this one.
I will take one variable for this one and I will take one variable for this one.
So instead of keeping instead of using this area, we can also use three variables to solve this problem.
So then our space complexity will become an.
If I'm using one day, I read in the space complexities big often.
But what if we lose, we will use aerially because in many problems, we cannot optimize space.
So that's why I make a habit of using it.
So what we are doing here?
Let's analyze our problem.
So what do we have so I have a problem I have and so this is my bigger problem and what this bigger
problem is doing, it is calling on two small problems to solve the problems.
So these are two suburb problems and minus one and and minus two.
And these problems will again do some work.
And this problem will also do some work and as soon as discussed these two problems.
Have some common book.
These two problems have some common work between them.
And what we are doing here, we are using an Eddie to avoid common.
So what we will do?
We will avoid the common vogue.
How can we avoid the common work we will store, that is so we will store and reuse.
Suppose there is some work and this work is also presented, so they will do the work and we will store
it here.
So then we will reach here.
We will likely return the result instead of doing the calculation.
So I'm avoiding the common work which is done by both these problems.
The work will be done only once and restored and we will reuse.
So this concept.
This concept is called dynamic programming.
Understood.
So what we will do so in the next few days, we will sell some more caution using the programming.
So I hope you understand the programming programming, any programming store and reuse.
Do not repeat yourself or do the work only once, store the result and use the result for future use.
Simple, I will tune the next one by.