Это видео недоступно.
Сожалеем об этом.
DP 4. Frog Jump with K Distance | Lecture 3 Follow Up Question
HTML-код
- Опубликовано: 10 янв 2022
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: atcoder.jp/con...
Make sure to join our telegram group for discussions: linktr.ee/take...
Pre-req for this Series: • Re 1. Introduction to ...
Full Playlist: • Striver's Dynamic Prog...
In this video, we have discussed how to solve the frog jump problem with K distance allowed. I have taught you how you should write a 1D recurrence. This problem is a follow-up to Lecture 3's follow-up question.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
![Gunna - today i did good [Official Video]](http://i.ytimg.com/vi/ulGLk8TaXcI/mqdefault.jpg)
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
Leetcode contest 275 solution????
Sir can we solve this question same as frog jump with i-1 to 1-2 one where you solved that question with tabulation method ...
What i want to say can we code this too as same as that one ?
@@rox_official9407 Yes that only i have explained here
US
nice explanation bro super🤗
I wrote the full code without seeing this video and it is exactly matching yours .Considering I have watched just 3 of your videos and I have started figuring out myself is amazing .You are DP King for me striver .Thanks for providing us with this much value packed content.
Same Bro I also wrote same code
Same here just used one less variable.😅 And got it in first run 🤯
Same bro
Same thing happened with me for his recursion series!
@@KalpitJain13.3 dengey
This is the best DP series I have come across, simple and precise after perusing several other tutorials on DP. Thank you Striver
Understood Completely. I watched the L3 yesterday and was figuring out in mind about the followup and by my own came up with the logic of looping and the (i-j>=0) conditions. Started building logic myself. Thanks Striver
I just realised to explain us all the codes, he actually manually writes all the codes with digital pen.
Which is so so much tougher than actually typing the code.
Big hats off.
For those who need basic code to start of this question
#include
using namespace std;
int helper(int n, int k, vector &heights) {
if(n == 0) return 0;
int minSteps = INT_MAX;
for(int j=1; j= 0)
l = helper(n-j, k, heights) + abs(heights[n] - heights[n-j]);
minSteps = min(minSteps, l);
}
return minSteps;
}
int frogKJump(int n, int k, vector &heights) {
return helper(n-1, k, heights);
}
int main(){
vector heights;
heights = {10, 20, 30, 10};
cout
THE BEST DP Series. UNDERSTOOD :)
Understood I just can't express My happiness that I am able to solve this question in all 3 ways(Recursive ,memoization , tabulation) Myself. Its just all because of You❤
Pseudocode at 6:43
Complexity analysis at 8:14
Memoization at 7:15
Tabulation at 10:15
space optimization at 10:55
"UNDERSTOOD"
DEAR STRIVER,
PLEASE TAKE CARE OF YOUR HEALTH.
thanks man for providing such a mindblowing content without charging even a single penny.Hats off to you
its literally after 2 years ,but still the best content in the internet so far :) "UNDERSTOOD":D
US... Thankyou sooo sooo much bhaiya for taking so much pain for us, even when you were not well. At first when I started watching this video, then I did feel that your voice was not having that zeal that you have in all your previous videos, and in the end, you made me right...nevertheless, take good care of yourself.
UNDERSTOOOOOOD ! you doing a great job ! And I am so so proud of you !
Take love !
Thanks striver for this excellent explanation.
Understood! I have been religiously watching all of your Striver A2Z DSA video series. The efforts and dedication that you've put into making these videos are themselves so inspiring. 98 more videos to go!
For the space optimization, use a LIFO queue with size K with arbirtrary access.
Deque
was able to do it competely by myself yesterday as you didnt uploaded the video.Take care of yourself!!
Very informative and actually the best series ..thanks a lot sir
bro i'm following up your a to z dsa course this is superb i usually do not comments but here i forced to because your content is ultimately superb thank you for it
Thank you Striver Bhaiya, I got the grasp of concepts & understood all the concepts taught in this video
Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥
Hey today is 30-09-2023 I am watching this lecture. I can not resist myself from completing this awesome playlist as soon as possible.
Thanks @takeUforward for this awesome playlist.
Striver ,the way you teach is really exceptional ✨
Please add leetcode link in description so that we can attempt it before the video starts.
Consider this request
bhai link de to rkha
dikhta nhi h kya
ye question AtCoder pe h
thoda leetcode ki jindagi se bhar nikal
@@champion5946 kyu bhai leetcode se kya dikkat hai
@@pool477 mene bola dikat h?
frog 1 & 2 AtCoder ka question h
secondly wo banda videos bana rha h
or link bhi wohi dhundke de tumhe 😂😂
@@champion5946 😂😂
Wonderfully explained, really appreciate your effort bhaiya, UNDERSTOOD.
Understood. Appreciate your efforts 💯
understood bhaiya thanku 💖
Highly appreciate the efforts for this playlist!!
Thanks a lot Striver! your explanation is too good 🔥🔥
"Understood". Thank you for the clear explanation in the earlier lectures, I solved this question in all ways(recursive, memoization and tabulation and even the space optimized one) even before watching the video. ♥
Excellent teaching Understood sir 🔥❤🔥❤🔥
understood! loving this series lately.
understood !!
crystal clear
"US"- Thankyou so much
space optimized version:-
int minimizeCost(vector& arr, int& k) {
// Code here
int n = arr.size();
vector dp(k, 1e9);
dp[0] = 0;
for(int ind =1; ind
By using priority queue , The time complexity reduced to O (N * log(k) ) , space - O(k)
No, you still have to push the K values inside the priority queue, so time will actually increase to O(N * KlogK)
Incase you find it difficult to code for optimized space that is O(k)
int frog_k_dp_opt(int n,vector &arr,int k){
vector dp(k+1,0);
for(int i=1;i
not working
Had fun watching this❤
DP and recursion... both are quite like magic for me
understood Raj bhaiyan, your surnames(Vikramaditya) suits to your reality, because you breain is full of knowledge!
Thank you striver , for this amazing dp series , i did this que by myself .
US
Nice explanation Striver
understood sir, thanks for such clear and concise explanations, hats off to you.
understood !!!
thanks for this amazing DP series...
I am able to think I the code immediately without seeing the solution. Thank you Striver for the good Dp series
Understood! Truly amazing series✨ Just by watching first two videos able to start thinking approach for further problems!! Thank you Striver bhaiyya for making DSA easier for us🚀
UNDERSTOOD............Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
UNDERSTOOD BHAIYA
understood perfectly
at 8:00. What is the time complexity of only recursive (no Memoization) approach.
Is it --> O(k^n).
yes
k^n
Understood , keep up the good work
Understood vaiya... plz don't stop making videos
Understood man REally hats off to you great effort
in the space optimisation part, instead of carrying a list, we can carry an array of k size such that every time when a new element's dp needs to be stored : we store it at the dp[index % k] position. This will overwrite the existing value in the dp array.
So the code in java will look like:
dp[0] = 0;
for(int index = 1; i
Understood Striver! Thank you so much for this amazing series.
Thankyou so much Striver , great explanation
Understand
understood !
UNDERSTOOD SIR
Understood ❤
Understood
If k was guaranteed smaller than N, it still wouldn't make sense to perform space optimisation due to the O(N) right shift required for array deletion and addition right?
Understood
Understood!
Thanks Bhaiya. Very nice explaination to this problem. Understood.
Understood!!! You’re doing a great job for us. It’s helping us a lot. ThankYou so much
Understood! thank you sir :)
Understood!!
Understood Striver, thank you.
understood
Great vedio bhaiyaa understood
Thanks Men! Hare Krishna
US
Thank you for the outstanding content.
the tabulation is not work, right? I try it and it not calculate the last index of dp[] because condition in second loop
j so it will not calculate it and always return 0
Time complexity for recursive solution is O(k^n)
Right!!
Thankyou Striver for all your efforts, great explanation :)
UNDERSTOOD!!!!
Much Appreciated Striver
code for space optimization:
def k_jumps(n,arr,k):
dp = [0 for i in range(k)]
if n == 0:
return 0
for index in range(1,n):
result = 999999
for i in range(1,k+1):
if (index > (i - 1)):
step = dp[k-i] + abs(arr[index] - arr[index-i])
else:
step = 9999999
result = min(result,step)
dp.remove(dp[0])
dp.append(result)
print(dp)
return dp[k-1]
arr = [30,10,60,10,60,50]
n = len(arr)
k = 3
result = 999999
print(k_jumps(n,arr,k))
Understood, wondeerful lectures!! A Big Big Thank You
#UNDERSTOOD! NO DOUBT THE BEST SERIES OF DYNAMIC PROGRAMMING.
understood. thank you for your efforts sir
understood bhaiya thank you so much
you are getting blessings of so much ppl
this level of content at no cost
Understood!!
I wrote 7 different meathod for the same problem, Amazing!!!.
😂
understood bro take care of u
tysm sir
5/57 done!!! Understood!
"UNDERSTOOD!!"
Understood :)
UNDERSTOOD
Understood ☺️
Understood.
Was able to solve without watching the video all 3 approach
"understood !"
Thank you! Understood:)
Understood 🤘🤘
Hats Off to your efforts 😊❤🔥❤🔥
Wow , did I just cracked a DP problem myself by only watching 3 videos.. Hail! Striverrrrr
UNDERSTOOD :)
understood sir.