Hey everyone, welcome back to the channel. I hope you guys are doing extremely well. So welcome to the third lecture of the dynamic programming playlist.
It's a wonderful question. Frog jump. So just to make sure you have watched the previous couple of lectures before attending this one because I have a perfect flow which I will continue. So if you're like if you're just watching this lecture three suddenly you might feel alienated.
So please watch out the previous couple of lectures. So what is the problem statement? So there is a frog.
on the first step of a n stairs long staircase. So the frog wants to reach the nth stair. Height i is the height of the i plus 1th stair.
So the array is given in terms of zero based indexing. So the energy lost in the jump is given by height i minus 1 and height j minus 1. So basically the frog can jump from the ith stair to the jth stair and the energy will be height of i minus one minus height of j minus one in the frog if the frog is in the ith staircase he can jump from either he can jump either to i plus one at stair or to i plus two at step basically he can take a jump to the one in plus one index or to the plus two index your task is to find the minimum total energy used by the frog to reach the first stair to the nth stair okay so that is what the question states so for an example i'll just take the first example 10 20 30 and 10 okay and i'll try to explain you this let's take the first example which is 10 20 30 and 10. so basically there's a frog now if i consider this as 0 1 2 3 the frog wants to reach from 0 to 3 i have converted the problem into zero based indexing so even if n is 4 it's ideally the question was from one to four but i've converted it into zero based indexing okay so if the frog starts from here and he can only jump one or two places what is the minimum energy that he will require okay so for example if the frog is here the frog is here and the frog says that okay i will jump from here to here then the energy that he will require is 10 okay and then he decides that he will jump from here to here and the energy again required will be 10 it's a difference of them absolute difference of them okay so if after that he decides that he will jump from here to here that's again the absolute difference which is 20 so this path will give him 40 the energy that he will take will be 40 let's let's try out some other paths what if i decide i will jump from here to here which will take me 10 what if i decide i'll jump from here to here so that again takes me a plus 10 correct So this path gives me 20 which is definitely better than the previous one. What if I decide I'll take this a couple jump because I cannot jump more than a couple of steps.
So this will be 20 and then I'll decide I'll jump one step so that will be a plus 20 again. This is again 40. So if you see I've tried out one possible way, two possible way, three possible way and the minimum that I encounter is 20 and you have to tell me which is the minimal what is the minimal energy that you can take and that is what the question is now uh can i say this can i say this that uh this question again gives me an idea that you are trying always so if you remember the previous lecture i told you if you are trying all possible ways then it's a recursion right and then you can either count always or you can find the best so can i say over here you're trying all possible ways way number one way number two way number three and you're taking the best possible and that's 20. why will a greedy solution uh not work over here that that might be a question that comes to your head so that's the first thing that i will be talking about why a greedy solution doesn't works let's understand that then after that we will think why we need to try all possible ways and need to take the best way out so when i say greedy that means you you are standing from 10 so you know from 10 you can go to 20 or go to 30. so you saw that if you jump till 20 that's the minimal so you jumped and from 20 uh you could have either jumped to 30 or to 10. both are taking 10 both are taking 10 so you can jump anyway so you jump this this is greedy basically when you are moving you try to jump the minimal possible jumps possible whichever takes minimal energy you try to jump that but why a greedy solution doesn't works let's check that out now when i say a greedy solution doesn't work so let's check this test case so if the frog was here if the frog was here Greedily from here he will try to move here because in moving here it will take him 30 it'll take him 20 The greedy option will be to move to 10. So, let's greedily move to 10. Which will cost him 20. Okay. Now, again from here, he can move here which is 50. Or he can move here which is 0. So, greedily he will move to 0. So, let's move to the 0. This will take him 0 energy.
Again from here, greedily he can move here which will cost him 40. Or this will cost him 50. So, greedily he will take the 40 stuff. So, he will move from here to here. Which will be again 40. so in total the costing will be 60 yes in total the costing will be 60. now what if i try some other way let's try that out if the frog is here and he decides he will be going till 60 that will cost him a 30 buck right and if he decides after that he'll go to 60 again that will cost him zero and after that he decides he'll go 50 that will cost him 10. so a total of 40 will be the costing a total of 40 will be the costing So we did realize the greedy way did not give you the correct path because you started greedily, but you lost out probably somewhere, right?
So that's why, that's why it's better if you try all possible ways, because sometimes it will happen that initially you took the better way, but you lost out on something significant like this 60 to 60 would have been zero. You lost out in future. So in such cases, 3d doesn't works and you have to try recursion now when i say recursion boils down to the second lecture what is over here recursion is try all possible ways so you have to try all possible ways okay so in order to try all possible ways you have to write recursion correct over here they're asking you which path did take the minimum energy so you have to find the path with the minimum energy correct and do you remember the previous lecture what was the step number one express the problem in terms of index do all stuffs on that index remember this to write recursion do all stuffs on that index step three over here they're asking you to find the minimum energy minimum energy that you took so take the minimal of all stuffs take the minimal of all stuffs this is how you write recursion okay so can i say i am wanting to reach the index n minus 1 i'm assuming zero based indexing so i'm wanting to reach the index n minus 1 so what do i want what does f of n minus 1 signify minimum energy required minimum energy required to reach n minus 1 from 0 index that is what the recursion will signify can i can i express the recursion in terms of index that's my first step i'd like yes you can how there are array indexes there are array indexes till n minus 1 so i'll consider every array index as an index so okay that's fine so i can be like okay that's that's absolutely fine so let's do it so can i say uh what will be f of 0 like common sense what will be the costing in order to reach from 0 to 0 that's going to be 0 because f of n minus 1 was stating the costing from n minus 1 to 0 so in order to reach 0 to 0 the costing will be 0 so i know one thing for sure that the costing for this guy will be 0 no matter what you do no matter what you do now let's so we have figured out what is the index that will be the air index next thing is do all stuffs on that index yes do all stuffs on that index now what is what what i what is the frog allowed to do the frog is allowed to either jump plus one or to either jump plus two so why don't you do that do all stuffs on that index please do it so what you will do is you will say okay i will do all stuffs on that index so if i do a single jump like i can say it as the left recursion so the single jump will say f of index minus one I'm doing this but if I'm jumping yes the question arises if I'm jumping from an index to an index minus one what is the energy that is being consumed I know in order to jump from index to index minus one the energy consumed is array of index minus array of index minus one that is what the energy is consumed can I say this is what the energy will be consumed to jump from index to index minus one and then i can ask the recursion hey recursion i have reached index minus one now it's your job to tell me from index minus one to zero how much it will cost you recursion will do the job i'll ask the recursion to tell what will be the costing from index minus 1 to 0 because i know the costing from index to index minus 1. i've taken that so that's what i'll do first i've done now can i say the right recursion will be very simple it will be if i take couple of jumps the costing this time will be a of index minus a of index minus 2 absolutely makes sense so i've done all the stuffs But I need to be slightly careful.
Can I do an index minus 2 always? The answer to that is yes, you can do it if it is not the first index. Because if you are standing at the first index, you cannot jump 2. Because that will take you to minus 1. You cannot jump 2. So you need to write a case like this.
If index is greater than 1, then only I can take the right jump. Otherwise, I cannot. Like makes sense because if you add the first index, you'll not be able to take the right job.
So that is absolutely making sense. So I'm like, okay, fine. That's fine. Now, what was the next step? Take the minimal because the question stated minimum energy.
Had the question stated maximum energy, you would have done it. Had the question stated something else, you would have done it. But in this, the question stated, find the minimum energy. So there is a way in which you jumped from index to index minus one.
There's a way in which you jump from index to index minus 2 and ask the recursion to find out the remaining answer So can I say you need the minimal answer? So you're going to return the minimal of left comma right That's how you can write the recurrence as I told you follow three techniques. You'll be able to write any recurrence relationships Yes, now you have written the recurrence relationship. That is absolutely perfect.
So we have understood the recurrence relationship now it's time to see if there are overlapping sub problems and how is this recursion actually working right so we know we know we are at f of 5 because if i write down the indexes it's like 0 1 2 3 4 5 so we know we are at f of 5 now at f of 5 where can we go we know that either we can take a jump to f of 4 or either we can take a jump to f of 3 that's definitely known to us so i can be like okay if i'm at f of 5 and there's this recursion call then the left recursion will be like okay f of 4 plus absolute of whatever height there is so what is the height 60 minus 50 there's this height of absolute 10 and then there's a recursion of right which is f of 3 plus again and height difference of uh these couple of guys which is 3 and 5 10 minus 50 is 40 so you can be like absolute of 40 now at first this recursion will go come back and then this will go and come back then you'll return the minimum of these right this is how the recursion is actually working so that's how i'm drawing the recursion tree so f of 4 will say f of 3 and f of 2 f of 3 will say f of 2 and f of 1 f of 2 will say f of 1 and f of 0 understood right so do you observe overlapping subproblems at least i am i'm able to do it by the way f of 1 will go to f of 0 as well i'm able to do it So if I mark the overlapping subproblems, there is one, first one, another one. So I have figured out if f of 3's answer I'm figuring out, then f of 3's answer why will I again figure out. So there are overlapping subproblems.
So if there are overlapping subproblems, can I say the answer to those subproblems will be similar. Thereby I can apply memoization to this particular recursion. Got it?
So I am understanding that okay I can definitely apply memorization. So you can easily apply memorization but I just in case to complete the recursion tree I'll quickly draw it. So in order to reach zero I'll take zero amount correct.
So f of one what would have what it would have done ideally in f of one was this recursion. So f of one went and there was a left recursion call of f of zero plus the jump from one to zero. So absolute of something. a jump from one to zero so absolute of something let's see one to zero will cost you 20 so you can add a 20. what about the right recursion can i say uh since we are standing at the first index there will be no right recursion because you cannot jump couple of index so i can say right is probably some bigger value now f of 0 will return you 0 for sure this will return you 0. so the left took 20 and the right took 20. so what will you return you return the minimum of both of them which is 20 comma let's assume this to be some int max max So it's 20 what you return as f of 1. Again, makes sense because if you are standing at f of 1, what is the cost that you will take from 1 to 0? That's one way.
There's only one way, which is 20. So that is what we have stored. Cool. So I have drawn this particular recursion.
Nice. Now we are at f of 2. So f of 2 would have called the left recursion as f of 1. plus a jump from 2 to 1 plus a jump from 2 to 1 which will cost him 50 so that costed him 50 and there will be a right jump which will be directly to f of 0 now there will be a jump from 2 to 0 which will cost him 30 so there will be a 30 now you remember f of 1 this had a value of 20 so it will return with a 20 so this guy gave him 20 so 20 plus 50 will give him 70 f of 0 will be how much 0. So, 0 plus 30 gives him 30. Which one will f of 2 give? The minimum. So, it will return 30. So, f of 2 got 30. Perfect. So, again, make sense because if I logically explain you, let me erase this.
If I logically give you an explanation, will this make sense? Yes, this will make sense because if I'm standing at f of 2, yes, if I'm standing at f of 2, there are a couple of ways. one is this one is this which will cost him 20 plus 50 which is 70 or the other one is this which is 30. so 30 is what you have got right now again similarly f of 3 when you're at f of 3 understand there is a left call of f of 2 plus the absolute difference which is from 3 to 2. so if you're going from 3 to 2 it's 50. so you can just take a plus 50. so what is f of 2 it has returned you as 13. correct what's the right jump the right jump is about f of 1 plus what now will you f of 1 so from 1 to 3 will be 0 1 to 3 will be 0 so plus 0. now will you go and do the recursion call of f of 1 will you go and do again f of 0 f of 1 is already computed you see it's just overlapping sub problem you can directly take the value from the dp array as 20. This gives you 20. This gives you 80. Which one will you take? 20 obviously.
So f of 3 becomes 20. Perfect. So remember, I'm storing the values of f of 3, f of 2, f of 1 in probably some DP array as you have seen in my lecture 1. Next, you're at f of 4. So if I'm at f of 4, what is that doing? It's again calling f of 3 plus absolute of 3 to 4 will be 50. So 50 and it's calling f of 2 plus 4 to 2 will be 0. So I can do 0. What's f of 3?
If I write what's f of 3? 20. What's f of 2? 30. So 20 plus 50 is 70. This is 30. Which one will you take?
Now, once you've written the recurrence, how do you convert a recurrence into a dynamic programming solution? That's the next question. How do you convert a recurrence into a DP?
So, that's when you say Memo I Asian okay, so take to apply my mission look at the parameters changing Yes, look at the parameters changing like which which parameters are changing. Just look at them. They'll be like striver There is only one parameter changing which is the one parameter. Let's come back.
It's index What is the maximum value of index? Let's look at the recursion tree five So you'll require a six size array because in a six size array there will be index 5 so you can definitely create a dp size of 6 over here which is indirectly dp of n plus 1. remember three steps step one is this declare an array of size n plus one step two before returning add it up dp of index before returning add it up store it and return step so this is step two what's step three Whenever you call an index, yes, whenever you call a recursion, check if it has been previously computed or not. If DP of index has been previously computed, no need to solve it again. Return DP of index, done. Line number three, converts a recursion to a memoization.
So I've converted a DP solution, converted a recursion solution into a dynamic programming. and if i talk about the time complexity what will be it one step two step three step four step five steps these steps are constant because these sub problems are not solved so these steps are constant five steps or n steps so i can say the time complexity to be big of n because there are n steps i can say there is recursion stack space of big of one and then uh and then rs is of big of and use this is how the recursion will look alike so it's now time to code it and probably submit it and after that we can optimize this into tabulation and after that probably into space optimization okay so in the code you're basically given n and you're given the heights so i know i know i have to write a recursion solution so probably i have to turn the in terms of index and let's carry the height as well but the java people uh you can easily code it because of explain the pseudo code while explaining so should not be a big issue for java people as well so i'll take anti function now i know the edge case is if index reaches zero i know the answer will be zero and i know there will be a left recursion call and i know there will be a right recursion call but we know one thing the right recursion call will always not happen so probably we can initially store that as intermax because this is not going to happen always if index is greater than one then we can have the right as f of index minus 2 and pass on the heights and then a plus of absolute of heights like you can just heights of index minus heights of index minus 2 that's something which you can definitely do and over here what you can do is the same stuff just make sure you copy paste and instead of index minus 2 do all the stuffs and that's how you do it at the end of the day what do you do you return minimum of left comma right correct now the question is uh very simple so you can probably say return f of n minus 1 because that's the last index and you can do on heights so if i run this will this run let's check it out okay so it says okay so intermax it is not ticking so probably we have to use hash include bits std c plus plus dot h generally uh like generally it is added over there not sure why they have not added it but not an issue let's quickly run this off so if i run it you can see so if i run it you can see the first three test cases are running fine and then there's a time limit exceeded because it's the simple recursive solution so how do you convert this into a dp convert create a dp array of size n plus one because that's the maximum initialize that with minus one now pass a dp over here just make sure you have a vector of int and you can just create a dp by reference Make sure always carry the DP. That's the next step.
Done. So step 1 of initialization and carrying on the parameters is done. What's the next step? Step 2 is storing the answer before returning for the subproblem F. Done.
What's the next step? If the answer has come across, just check this and return DP of index, right? So if I just do these changes and if I now run, bingo! Works fine. All the test cases.
If I submit them, you will see it's absolutely correct. So this is how you can do the memoization stuff very very easily. So in the first lecture I told you after memoization, it's very important to understand how do we do the tabulation one and after that we will do the space optimization.
What is memoization? Top down, why? Let's understand.
So in the recursion, if you observe what did you do you had a top portion but first the down answers like you went from top to down correct what is tabulation it's the exact opposite yes i repeat it's the exact opposite bottom up okay that means you'll start from the bottom and you'll go up so always look at the recursion tree always look at the recursion tree what's at the bottom yes so you'll go up and then you'll fill it you'll take 0 you'll fill 1 then you'll fill 2 then you'll fill 3 then you'll fill 4 you'll fill 5. it'll go from the bottom to the so that's tabulation understood now what did i tell you in tabulation what's the first step step one is to see in memoization how much dp already did you use we know we used a dp array of size n plus 1 so just without thinking anything you can initialize that okay so without thinking anything you can initialize that by the way uh it will be n like even if you initialize n it will work because we have used a zero based indexing so make sure everything is initialized with minus one or you can initialize that with zero doesn't matter over here so first thing is done what's the next step look for the base case because in recursion it will stop down it over hits down top like bottom up so what's the base case let's look at it the base case states index equal to equal to zero returns you Index equal to equal to 0 index equal to equal to 0 so whatever is that you'll write that EP of 0 is equal to 0 Just write it after that just look at the recursion state these lines When will it be executed I can be like it will be executed at 1 2 3 4 and so on till n minus 1 of the index Makes sense because the worst call worst call that I'll make will be n minus 1 so it will be executed for sure I'm like yes, so please write it i equal to 1 till n minus 1 run a for loop perfect what's the next step just go and look at the recursion what am i doing what's the what's the stuff done on the index yes replace this with dp and write it so the first step is very simple i can say if i take first step it will be dp of index minus 1 plus absolute of array of index minus array of index minus one simple I can say second step will only implicate if I is greater than one remember super super second step will only implement if that's true so DP of index minus 2 plus absolute of a of index minus a of index minus 2 as simple as it gets and what do you store store it dp of index will be minimum of dp of index minus uh sorry uh dp of first step and second step as simple as it can get and if you write this it's definitely going to work wonders so i'll try to show you over here like i'll just erase this And over here, if I just write the same thing, like you'll see over here, if I try to write the same thing, like I'll write dp of 0 to be 0 for int i equal to 1, i lesser than n, i plus plus. And I can write int first step will be very simple dp of i minus 1 plus absolute of heights i. minus heights of i minus 1 right and what about the second step i can say the second step will be very simple i can initially keep it as int max correct and what i can say is second step will only be implicated if index is greater than 1 and the second step will be nothing but dp of i minus 2 plus absolute of heights of i minus heights of you i minus 2 as simple as it gets and the dp of i will be minimum of dp of i minus 1 sorry minimum of first step comma second step and what do you need to return you need to return the answer will always be stored at the last index and thereby if i just take this off now and now if i try to run you see it's running and if i try to sum it works fine so We can convert this into tabulation so easily by a recursion can be converted into a tabulation.
Now the question arises, can we reduce the space? Because over here, we are definitely reducing the stack space that we used over here. This is reduced, but there's still a big of n being used. Because as you can see, we are still using a dp of n array and the time complexity cannot be reduced.
But can I omit this? Let's see. can we omit this i did tell you one thing anytime there is something like index minus one index minus two there can always be an space optimization take this as a thumb rule there will always be in space optimization if there is something like index minus one and index minus two always these states can be now let me tell you something assume you are at index zero one two three four and so on till n minus one okay initially initially assume just assume you are over here and this is nothing but dp of i and you're saying this as dp of i minus 1 and you're saying this as dp of i minus 2 you're saying correct in the next step whenever i will increase can i say that i will go over here and this will be dp of i this will be dp of i minus 1 this will be dp of i minus 2 indeed i can there's no doubt i cannot in the next step Can I say this will be DP of i, this will be DP of i-1, this will be DP of i-2? There's no doubt. So, do you observe a pattern?
The guy who was DP of i-1 for this particular i, in the next step, in the next step, when the i increases to the next index 3, the guy who was i-1, that means he has the previous. He'll become the second previous of the next. He'll become the second previous of the next.
makes sense so he'll become this so can i say dp of i minus 2 will become this right so do you need to carry a array can't i do this using couple of variables like think can't you do this using couple of variables the answer to that will be yeah i think we can because what we require at any particular instance i is the previous guy and the second previous guy i don't need anything more why the hell do i need to declare a dpra I don't need anything else. Thereby, I can say, okay, so that makes sense. Let's assume I do it this way.
This is car i. I say this is previous i. And I say this is previous to i. Instead of storing them into an array.
In the next step, I know this will become car i. I know that car i will become previous i. I know the previous i will become previous to i.
So can I just use couple of variables where I say previous to i for the next step whenever you have done all the stuffs. The previous i will become the previous to i because whoever is previous will become second previous for the next step. And whoever is the current guy like whatever is the value of dp of i that will become the previous for the next step. So if you just keep on doing this you will no more require anything. So can I say this?
instead of dp of 0 can i carry a previous equal to 0 uh makes sense i can and can i carry a previous uh 2 equal to a probably 0 as well because for the first for the first you'll require dp of index minus 1 which i can represent as previous now correct and this i can represent as previous 2 because that is what we recommend and after that can i say in the next step the previous 2 will be previous and the previous will be nothing but Ker-I and this guy will be Ker-I Make sense? Make sense? And what will be the answer at the end? Whenever you exceed, I will go beyond n minus 1. And whenever this for loop ends, the value of I will be n. Yes, the value of I will be over here.
And for this guy, for this guy, previous will be at n minus 1. And you always required the answer of n minus 1. So you can say whatever is the answer for previous will be your answer. So you can easily print. the answer as previous so if you do this you will be able to get your space optimized and you'll no more be requiring a dp array so if i try to write this in the code probably i'll delete this and i can keep a previous equal to zero i can keep a previous or two as well as zero and i can just omit this to previous and i can just omit this to previous two and I can be like this to be curr and I can see the previous two will become previous now and the previous guy will be for the next step will be curr correct and at the end of the day instead of dp of n because I will be at n minus one so I can definitely return something as previous so we run this here it works let's submit it is working fine So we have done a space optimization. Yes, we have done a space optimization.
So this is how this problem can be easily solved. So this is how I can space optimize it. I hope you have understood the space optimization. Now there's a follow up to this wonderful problem.
Okay. Now this question stated you can jump to I plus one and you can jump to I plus two. That's the maximum that you put. Now the follow-up states the follow-up states there can be k jumps yes the follow-up states that there can be k jumps now instead of i plus one you can jump to i plus one i plus two i plus three till i plus k that's what i'm saying so if i change the question to this can you solve this problem now i'll give you this as a homework okay so take this question as a homework uh i i want you to do k jumps if you if you are using k jumps then probably you cannot use space optimization because then there will not be couple of stuff there will be k uh previous elements that you have to carry you will not be able to use uh stuff that i told you but yeah uh the stuff that i gave you was the follow-up is very simple try to do it using k jumps i will expect the quotes in the comment section and i'll be discussing this problem right before uh starting the lecture four right before starting the lecture four I'll definitely be discussing this problem k jumps where I'll tell you how to change this problem slightly and you'll be able to do this problem for k jumps so guys if you have watched this video till now and if you've understood everything you know what to do this is what I expect even if you are very very very lazy please comment us us means understood and this is something which you should always do you're watching these videos because it takes a hell lot of effort to make these kind of videos And yes, if you're new to this channel, please, please do consider subscribing. And please do share this channel among your college mates, friends, wherever you can.
And if you haven't checked out our SD sheet yet, oh man, what are you doing? There's an SD sheet link in the description. Go and check it out. That's the ultimate resource for placements, man. And yeah, with this, let's wrap up this video and probably meet in the next one tomorrow.
Bye-bye.