Hello, everyone.
So in this video, we'll discuss the question we know steps to one show in the last year days we implemented
a solution.
Now we will check.
We will do there occasionally and we will check whether there is any repetition or recalculation.
So if there is any repetition or recalculation, then we can use the memorization technique, the top
down.
So let's see.
So let us take an example to the value of industrial.
So 12 will call on 11.
So tell us why do so?
We can also call on six July three.
So it will call for now for 11.
Obviously I can call 11 is Nahdlatul by two.
So no call 11 is Nahdlatul by three.
So no call at all.
Six.
I will call on five.
Six is Dugal by two so I will call on three and six is little by three so I will call on two forfour.
I can call on three.
For four voyages, so I will call on to four is not dizzle by three, so no call at all.
Now 14 I will call on nine, I can also call and five.
I cannot then is not a celebrity, so at done so for nine, I can call on it.
So nine is not DL by two, so no goal line is DL by three.
So there will be a call three.
Four, eight, seven, eight is decided by two to four, then no collar at all, so for three, call
two and then two is not easy by two and then three is decided by three.
So it will be one and similarly four, then it will be no collar at all and no collar at all.
And similarly, you can complete dedication.
Three.
OK, so it will continue to go on.
Now let's see if there is any repetition.
So for I am calculating for again.
I'm calculating for.
Again, I have four.
Then similarly, I have five, five, similarly, we have three, three, three, then again two to
two.
So basically there is repetition and we are recalculating our answer again and again.
Now, let us discuss the complexity of our recursion method.
Now, in the worst case, what will happen?
So each node will call on three nodes and minus one and my two and and rightly so, if we will blindly
call three calls for each.
And also the time complexity will be thrilled about it.
So obviously, this is not the correct time complexity.
So we can assume on an average our function will call on to other function calls.
So we can say on an average the time complexity to the power.
And basically it is it is definite that the time complexity is exponential.
So this is very sure there are time complexities, exponential.
So that is very short.
Now, this is very, very bad.
Exponential time.
Complexity is very, very bad.
Not if you will try to understand how many unique calls are there.
How many unique calls are there?
So basically, I have to reach from 12 to one, so the unequals will be 10, then 11, then 10 basically
in this fashion, so unique calls will be to alonely basically I want to reach from nine to one.
So total number of unique calls is simply big off end and calls total number of unique calls especially
and calls and and each function we are doing constant work.
So if you will see in each function.
So all this is constant work, OK?
So all of this is constant work through the number of calls is the total amount of time complexity.
So the unique calls are basically big often and the rest everything.
Rest of everything is repetition, that stuff, all the calls are repetition and recalculation because
this big often.
So what we will do so obvious solution when you are calculating for what you will do, you will save
your answer at this point.
And then when you need to calculate for it again, you will likely return your answer from here.
Similarly, when you need to find out support for, you can likely use this answer.
OK, so again, what we will do, we will calculate.
We will calculate only once, then we will save and we will return.
OK, so let us write the memorisation code.
So memorisation means top down DEPI.
So what is our approach, what we will do?
So for starting the answer, we need, Eddie.
So what will do, we will construct Benetti.
Plus one side, so the first and next will be zero and the last.
And so this is the next and the last index will be and plus one.
And again, we have to initialize this area.
So I have to initialize this area with invalid answer.
So let's initializing this area with minus one.
So why minus one, because minus one is invalid answer.
So you have to initialize this area with any invalid answer.
So minus one is invalid answers.
Why missionising it with minus one?
You can also initialize it with minus two, minus three.
Anything, for example, like initializing this area with minus one.
Then let's say this is index A.
And let's say the name of this is answer, so what does onset of I contains?
What does the meaning of of I so answer of is basically the minimum steps required to reach.
From one to a.
OK, so this is the meaning of onset of a minimum steps required to reach from.
I to.
And what do we want?
We want to find out the minimum steps required to reach from nine to one.
So basically my answer will be answered often.
So this will be my big answer.
This will be my big answer.
So this one, this value, this indexes and the size that is in place.
And so this index is in and this will be my answer.
I will return this answer.
So this is minimum steps required to reach from end one.
So now we are ready to write the code, so let us write the code.
So end.
The name of the function is Lizzi M. Steps.
Do so again, it will take and as input now what we have to do, we have to construct an area first.
So let us make an.
So instead, you can call it on set or you can also call it DEPI, it's your choice.
So let's say I'm calling a dancer.
What about the size of that issue as discussed, the size of that is and plus one that would have to
do so, we have to initialize this area.
And we have to initialize the area with invalid answer.
So any invalid, valuable work, so you can write it like minus two, basically any invalid value.
So let's say I am writing minus one because minus one is invalid answer.
And what will do?
We will return the helper function.
We will write a helper function.
We will call that helper function.
We will pass and and we will pass Ansary.
So now let us write the code for helper function.
So the return type of helper function is in Pejar.
So what this helper function will take, it will take two things, NT and Eddie.
Let's say the name of that is answer.
Now we have to write the code here, so what we will do, we will copy paste the same code.
So this is the old Goldrick government or this called.
And save the school now, what changes we have to do, so, again, the best case will be we'll see
if the value of any is less than close to one, you can return zero.
But here you have to write one more case if the value is already calculated.
So basically, if I.
Seraphin.
It is not equal to minus one, so reinitialize that if it minus one, so if the of mind is not close
to minus one, that means we have already calculated our answer.
OK, so here what I'm doing.
So here I am checking Jacov output exist.
So let us check if output.
Already exist, so if output already exist, then you can it return the output.
So if I said if I start to question my nisson, you can like Leader Dunn answer because we have already
concluded the answer.
Simple.
Otherwise, what we have to do.
Same Golodryga solution X, Y and Z will be the maximum, then Kolon no header near the function is
helper.
And minus one, and we have to pass the answer ready?
Again, the name of the function is Helper and by two they will pass the answer ready.
So here the name of the function is Helper and Maitri.
And possibly on Saturday, then we are calculating our answer.
So this is my answer, but you cannot answer.
You have to first save your answer.
So what do you have to do?
It will save you an answer for future use.
OK, so one thing, the name of the name of the variable is also on set and here it is also on set.
So let's change the name.
So let's make it.
Output.
OK, so what do you do, you will return output, but first you will see your output.
So first save, so I said often we are saving the answer for future use.
And then you will return your output, so let's call this function M. Stepstool.
And let's pass the value of an.
So let's test our record.
OK, so this one.
Let's say the value of an is 11.
So foreign for OK, so the first one is due to the recursive of and the second one is due to this memorisation
called.
So this approach is basically called top down DEPI.
Why this is called top down, because first we are moving in this direction and then we are moving in
this direction just like Fabianski.
So this is called top down DP.
And the name of this is basically memorisation.
What is memorisation memorization is you simply write the recursive code and then you will your result
also.
So basically we copied our recursive code and then we are just storing, I said before returning.
So we're just starting our answer before returning.
So what about the time, complexity of the solution?
So let's take a small example.
Let's say the value of it is six.
So what will happen?
Six will call on five, five and then four.
Four will call on three.
Three will call on two and then two will call on one.
So what will happen?
When is the best case.
So when will it and its answer then.
Two by two.
So I'll call on the right hand side when one is the best case, when will it answer then it will happen
to its answer then three.
So by three.
So it will call on one.
So when is the best case?
It will likely be done.
Its answer then three will return answer to four.
So four is resolved by two.
So there will be a call until now.
At this point when we are returning the answer, we will also see the answer for two so we already know
the answer for two.
So very directly written, the answer simple.
Similarly, when we are returning the answer for three, I will answer for three.
Now I will answer for four.
So I will store the answer for four.
So, five, it is now reduced by two or three, then four, six, six is dugal by two, so it will call
on three and six by three.
So they will be Ashqelon, two for three.
We already know the answer.
We have stored the answer here, so we will directly return the answer now for two, we have already
stored the answer here.
We have already calculated and stored the answer, so we will likely return the answer.
And finally, thirty five will also return the answer.
Then six will call Continental and we will also slow down to four five.
Then we will store the answer for six.
So we are storing the answer for six and then we are returning our answer and then we will return the
answer.
So how many total number of unique calls?
So total number of unique calls is basically this one.
So they are basically unicorns, so the value of animal sex, that's why succinylcholine, so the complexity
is basically big, often you will see in each function.
So this is constant, this constant, constant work, constant work, constant work.
So each function.
Is doing constant work and total number of functions called total function is called.
It's basically big off, and so what is the time, complexity, so total function called multiply burdened
by each function.
So that's why the time complexity is big.
Often see by using memorisation our time complexity becomes linear.
Earlier due to recursion, when we was when we were using alligations or time, complexity was exponential
due to the power.
And we can assume that on an average there are two goals.
So that's very true to the power.
And so from exponential, we are able to reach linear time complexity.
So that is the power of top down beyond memorization.
So I will see you in the next one by.