DP 3. Frog Jump | Dynamic Programming | Learn to write 1D DP 

I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.

2 years later. Still the ultimate and unbeatable learning resource in the market.

this is the only playlist on youtube where you will find only positive comments because this man really put his effort to make this playlist valuable. thank you so much striver.

Best video I have ever seen on DP. Thank you Striver for helping out fellow developers.

The dp series is like web series. Every day a new episod is coming with lots of new things and leaving a suspence for the next one.. thank you striver for this wonderful effort..and "UNDERSTOOD"..

This series is so damn good that before watching this video, i thought of giving "min cost climbing stairs" question on leetcode a try because i felt i could do that. That is similar to this question only. And boom, i solved that question in all possible ways...recursion, memoization, tabulation and space optimised method. Thank you striver. You have kinda opened our brain and made our thinking broader. Thank you so much for the inspiration you are. Love you !!!

Hey, striver i just want to say that concept in your videos are such a crystal clear and easy to understand that even i am studying for the first time i do not feel any difficulty to understand the solutions. so, thank you so much for providing such a video lecture free on youtube

your explanation is so good that even before you write the pseudo code, i was able to write the recursion by starting from 0 to n-1 rather than the reverse approach that you have taken in the video. Great Work you are doing. Helps to improve the way a person can solve a problem.

Amazing video! Do watch till the end because in the space optimization part, the actual value of watching the past two videos comes.

UNDERSTOOD , Now I am loving dp its become easy to think from recursion to tabulation step by step, thank you so much for the hardwork!

Thanks so much Striver. We really appreciate your effort. You are a rare gem.

Understood!! After seeing the recursion, I was able to convert it on my own into a dp. Thank you STRIVER. ❤

Understood, Honestly this is the very first time I am trying to learn any dp problem. And I am able to understand everything... Very clear explanation. Loved it.. Thanks a lot for all the efforts :)

I recently started this dp series and i want to complete this series in 20 days this is my day 1 Thank you for this awesome series

You will get hired even if you can explain an interviewer till memoization thing but it will blow the mind of interviewer if you go till space optimisation to constant.... awesome video and striver is just god.

Amazing the content the quality the explaination taking students through the journey from greedy to memory optimized dp in such a simple yet elegant way Genuine appreciation Man

Recursion code at 24:33 Memoization code at 25:25 Tabulation code at 30:54 Space optimization at 36:22

Understood! Your series is making me love DP. Thanks a ton! Excited for the next one.

Understood, Now I'm loving Dp Thank you Striver ❤

I am nothing but greatful. Wanna finish the whole playlist. Thanks a lot

Hey Striver! I tried solving this question myself and I was able to solve it, I must say this series is amazing. You started building my concepts in first 2 lectures itself. Gonna see your lecture now and look at your approach. Would surely complete whole dp series. Thank you for this series ❤

You explain these concepts so well! Thanks man!

I also started understanding dsa , you are magical man of programming world✌

Very helpful and minute problems were explained nicely. Nothing best than this.

understood the thought 💭 process and that's what I wanted...thanks a lot brother!

We will take a for loop running from j=1 to k and instead of writing (ind-1) and (ind-2) we will going to simply write (ind-j) that will give me the solution. Time Complexity:-O(N*K) Space complexity:-O(N). Yes sir, it cannot be space optimised because we have to use K+1 variables . Nice video and yes you are absolutely right, I have learnt space optimisation in dp from you THANKS MAN 👍👍

Understood! Thanks for explaining beautifully!

Clearly understood💯. Thank you so much for the series

Amazing video! Everything is clearly understandable. from day 1 of dp series I have watching your videos and Day by Day become big fan of your teaching way. God bless you sir. Came to know from your insta story that u have fever 🤒 Get well soon sir.

follow ups solution: #include int frogJump(int n, vector &heights, int k){ vector dp(n, INT_MAX); dp[0] = 0; for(int i=1; i

Understood. Amazing explanation. Thanks a lot for making these videos.

Understood! Also, I could do tabulation and space optimization on my own after watching the explanation! A very big Thank you🥺

At 25:23, can't you initialize the dp array for only n elements instead of n+1? Like you did for tabulation?

Code Of Frog Jump #include using namespace std; //Top-Down Approach int dp1(int ind,vector&heights,vector&dp) { if(ind == 0) return 0; if(dp[ind] != -1) return dp[ind]; int left = dp1(ind-1,heights,dp) + abs(heights[ind]-heights[ind-1]); int right = INT_MAX; if(ind > 1) right = dp1(ind-2,heights,dp) + abs(heights[ind]-heights[ind-2]); return dp[ind] = min(left,right); } //Tabulation Method - Bottom Up Approach /* vectordp(n,0); dp[0]=0; for(int i=1;i 1) secondstep = dp[i-2] + abs(heights[i] - heights[i-2]); dp[i] = min(firststep,secondstep); } return dp[n-1]; */ //Space Optimization /* int prev=0; int prev2=0; for(int i=1;i1) secondstep = prev2+abs(heights[i]-heights[i-2]); int curi = min(firststep,secondstep); prev2 = prev; prev = curi; } return prev; */ int frogJump(int n, vector &heights) { vectordp(n+1,-1); return dp1(n-1,heights,dp); }

Understood!! Thanks a lot for creating this series.

Understood ! much appreciations to your efforts .

UNDERSTOOD 😀🔥

Can we write base case for n=1, then can write Math.abs(heights[1]-heights[0])?

"UNDERSTOOD" Great series Striver

I managed to do the space optimization on my own! That's just how good your explanation is!

The code for k jumps: #Memoization def k_jumps(n,dp,arr,k,result): if n == 0: return 0 if dp[n] != -1: return dp[n] for i in range(1,k+1): if (n > (i - 1)): step = k_jumps(n-i,dp,arr,k,result) + abs(arr[n] - arr[n-i]) else: step = 9999999 result = min(result,step) dp[n] = result return dp[n] arr = [30,10,60,10,60,50] n = len(arr) k = 3 result = 999999 dp = [-1 for i in range(n)] print(k_jumps(n-1,dp,arr,k,result)) #Tabulation def k_jumps(n,arr,k): dp = [-1 for i in range(n)] if n == 0: return 0 dp[0] = 0 for index in range(1,n): result = 999999 for i in range(1,k+1): if (index > (i - 1)): step = dp[index-i] + abs(arr[index] - arr[index-i]) else: step = 9999999 result = min(result,step) dp[index] = result print(dp) return dp[n-1] arr = [60,30,10,60,10,60,50] n = len(arr) k = 3 result = 999999 print(k_jumps(n,arr,k))

Count all possible palindrome in string with rearranging characters - Infosys 🙄

understood every bit of content ...thank u for this amazing lecture

Thanks a lot!!!! I was able to solve the video without seeing the video all because of you!!!!

"UNDERSTOOD"..... Bhaiya pls upload practice problem link other than coding ninja link. Leetcode interface is best for easy understanding. I hope you understand , Thanks

Solution of follow up: Approach: 1. Maintain a Linked List which will contain AT MOST K nodes, (analogous to DP array of size K) 2. For i'th state, traverse through the linked list to access previous K dp states to find the minimum energy required for the jump. 3. Now, to store the result, a. if LinkedList already has K nodes, then i. remove the HEAD node from list ii. update HEAD iii. to store the result and attach it to TAIL. b. else, i. create a new node and attach it to the TAIL of the linked list. Note: This is the reason Linked List is used instead of an array to shift the elements in O(1) time. Note: We can use Queues and Iterators also for the same purpose, but memory reuse won't be possible. Time Complexity: O(N*K), Space Complexity: O(K) Code: public class Solution { static FrogKJumps obj = new FrogKJumps(); public static int frogJump(int n, int heights[]) { return obj.minJumps(heights,2); } } class FrogKJumps { static class Node { int val; Node next; Node(int val) { this.val = val; } } public int minJumps(int[] heights, int k) { if (heights == null || heights.length < 2) return 0; Node[] headTailRef = { null, null }; // 0th index = head, 1st index = tail boolean hasAtLeastKNodes = false; headTailRef[0] = headTailRef[1] = new Node(0); for (int i = 1; i < heights.length; i++) { int j = Math.max(0, i - k); int minEnergy = Integer.MAX_VALUE; Node nodeItr = headTailRef[0]; for (; j < i; j++, nodeItr = nodeItr.next) { minEnergy = Math.min(minEnergy, Math.abs(heights[i] - heights[j]) + nodeItr.val); } append(headTailRef, hasAtLeastKNodes, minEnergy); hasAtLeastKNodes = i >= k - 1; } return headTailRef[1].val; // analogous to dp[n-1] } /** * if willEvictHead is true, then uses the current head node as next node * (analogous to FIFO replacement strategy) * else, a new node is created and attached to end of linked list * * Assumes, linked list contains at least one node */ private void append(Node[] headTailRef, boolean willEvictHead, int data) { if (willEvictHead) { Node head = headTailRef[0]; head.val = data; headTailRef[0] = head.next; headTailRef[1].next = head; } else { headTailRef[1].next = new Node(data); } headTailRef[1] = headTailRef[1].next; } public static void main(String[] args) { int[] heights = { 4, 8, 3, 10, 4, 4 }; int k = 2; System.out.println(new FrogKJumps().minJumps(heights, k)); } } Github Gist: /SujanKumarMitra/0544d830e41ca55f858976fbbb5a7491

Best explanations indeed, love you man.

This playlist is worth the hype ❤‍🔥

If possible pls provide leetcode problem link also of the particular problem since most of us are following leetcode

Bro the way u explained is just amazing

understood and sir this is the best series till date i found

this space optimization technique is way too classic, thanks bhaiya

Understood. Great Playlist !!!!

Amazing explanation. Perfect solution to explain in an interview..

Perfect, Thanks a lot Striver

Understand. Keep doing good work striver

Understood, Thanks a lot bhaiya ❤

UNDERSTOOD. Your explanation is damn good bro. thanks alot.❤

I think it is the best solution to previous videos

US😎 Before the lecture, i was having a lot of fear about tabulation. Bt now its totally clear.😇 Thanks Raj Bhaiyya

Understood! Just wow! Love DP ❤️

Explanation is very high level❤❤❤

understood this very well. Thanks to striver

Understood each step in detail 💯

Thank You Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

US , such a cool explanation ... thnx for this wndrful playlist

Thanks baiya very wonderfull video. I understood the video. Please make more and more videos. God will bless you. HK.

Understood! hauuwa bana rakha tha dp ka 1 saal se man mein thanks 900

understood. Thanks for DP web series with addiction

awesome, loved the clear n cripsh explanation

Great explanation striver!! Understood

Understood....Thank you so much :)

Love the way you explained

Understood , Thanks Striver

understood Sir... U are just GOD

I am actually watching this to give a google interview sometime later but god damn, this is actually fun to learn lol

Great Teaching Striver!

By watching this series ....i feel i started something in my feel

Awesome Series Kudos !

Learnt the concept, went straight to the editor, coded it in JAVA and submitted it...All test cases submitted 🔥👍 Striver's way of explaining recursion and DP is unbeatable and uncomparable

Approach: Since the frog can make k jumps, we can use k recursive calls and find the minimum of them. used a variable ans to kept it as positive infinity to update the answer . base case is same as the frog jumps qn. but since frog can make k jumps, used a for loop to find the the answer for every jump (1st , 2nd ,.... till kth). also a check of i-w>=0 is made so that there is no infinite recursion. def frogJump(n,heights,k) -> int: i=n-1 ans=float('inf') def helper(i,ans): if i==0: return 0 for w in range(1,k+1): if i-w>=0: find=helper(i-w,ans)+abs(heights[i-w]-heights[i]) ans=min(find,ans) return ans return helper(i,ans) def frogjump_tabulation(n,heights,k): dp=[0]*(n+1) dp[0]=0 for i in range(1,n): ans=float('inf') for j in range(1,k+1): if i-j>=0: find=dp[i-j]+abs(heights[i-j]-heights[i]) ans=min(ans,find) dp[i]=ans return dp[n-1]

best and detailed explanation ! thank you :)

4/57 done!!! understood!

big thank you bhai for your hard work and make questions easy for us , again thank you with saying "we can't be lazy by seeing your high level of energy to teach us", "UNDERSTAND" 😍🥰🤩😇😘❤💘

Thank you, understood very well

UNDERSTOOD. Thank you very much

yeah, Sir, I understood. your lecture is very informative..... thank you, sir.

great explanation like always

Nice series Striver. Thanks

Great explanation.

UNDERSTOOD...........😎😎😎😎😎😎

UnderStood Very well Thank You sir

thanku striver bhaiya

semester 1 is about to start,and i am on this lecture,super confident>3000

very well understood !

Awesome... Thank you for your efforts. totally Understood :)

I understand well and good thank you so much...

you are great sir now i am easily understanding dp thankyou so much

Understood very well

Understood, thank u very much Sir for nice explanation 🥰