Understood Sir. At 3:50 min of the video I paused it and went to the recurrence playlist, then watch lecture no 6 & 7 thoroughly and then came here .Amazing session .Thank You Sir for helping us to improve our skills.
Believe me I have been trying to solve dp problems since 6 years and never came across this playlist. Amazing learning technique. This will surely help me in cracking interviews.
I got confused when you wrote f(ind) at 7:57. Immediately, the pop up rectified the mistake. It's amazing how much work has gone in these videos! I'm loving the playlist till now! Keep up the good work man. Your inputs to the community are huge and they will definitely return back to you in one way or another. Best wishes!
Today I had my Amazon interview and I got this exact questions and after completing the striver's dp series I was fully able to solve all the approaches and explain it to the interviewer so clearly and he was impressed by the way I explained the approaches and the time and space complexities! THANK YOU STRIVERRR!! You are the bestttt🎈
Initially I was not able to understand anything related to DSA. I thought that I am not for this. But when i started seeing your videos I found that what I was lacking was a good teacher who is able to understand such advance complex concept in matter of minutes in the best simple way possible. I would have never imagined myself solving hard level dsa questions without you. Thank you sir for all your efforts . Please continue teaching. We will be always with you. THank YoU.
Hats off to this guy whenever we discuss about dp, people just start with tabular method no one teaches how to apprach that, what is the intution behind that approach but this guy making the concepts crystal clear. Thank you so much bhaiya😇
I can find the recurrence relation of a problem and determine whether it is a dynamic programming problem by determining if there is any overlapping sub-problem. The interesting fact is that I have learned these from this playlist. Thanks a lot, bro.
I think we can write one more base case for index = 1. Like 0, when 1 is reached then it means element at 2 wasn't selected and we want to maximize sum so we can select either nums[0] or nums[1] so return max(nums[0], nums[1]) as we need to maximize sum. By doing so we can omit the line that is returning 0 when n < 0 Thanks Striver, Wonderful explanation!
I never had a habit of commenting. But the way you are teaching makes me enthusiatic towards dsa understood each and every concept following from array to dp was a long journey. It wasnt possible without .once again thank u bhai❤
Its good to watch good content for free.. I just finished recursion playlist and now watching DP. For me it is a hard topic, tabulation technique is most difficult but i hope i will get it by the end of this playlist. (NON-CS BACKGROUND)
Understood..You make learning fun :) I am done with my interviews but still don't want to miss learning any concept.This has never been me but all thanks to you :) You're indeed doing a great job!!!
In space optimizations, it's better to initialise things like this: int pre1 = nums[0]; int pre2 = nums[0]; int curr; Just because this makes more sense.
bhaiya you are the best i mean i was confused with dp for so long time and this was becoming the only topic which I was afraid to cover but now my concepts are getting clear and thankyou so much for this series at this time since this will help me do goood in my internships thankyou bhaiya 🥰🤩
it was literally the best series . i am myself to able to code recursion problems now and its boosting my confidenece and also bhaiya the space optimisation part is just awesome yar
Understood buddy. As usual, great explanation. Get well soon too. Just a request. Need a little more clarity on how to identify whether to approach as a greedy algo or dynamic programming pattern just by looking at a problem.
Generically if u see greedy failing, switch to trying all cases by recursion. For this u need your brain to generate test cases and figure this out that greedy is failing.
As much as I can think if the data is sorted and have uniform difference between them then I think we can go with greedy else dp Correct me if I am wrong plz
@@aakashagarwal146 not uniform but some sort of increasing difference In coin change problem greedy works for 1,2,5,10,20.... becz difference is 1,3,5,10 which is in order and not overlapping but in cases where difference is overlapping or not in any order like when coins are 2,3,6,7. here greedy fails becz the difference is 1,3,1 which is overlapping hope you got the idea
Bhaiya Codestudio platform is lagging many a times , could u please provide problem links of similar type that are available on gfg , leetcode , codeforces, codechef etc for practice
You explained so well, dp was to be hard topic for me but after watching your videos the thought just reversed. Keep going. Most hardworking man i ever seen.
Understood perfectly, It has been so easy now to convert recursive code to Memoization, Tabulation and then space optimization approach Thanks A Lottt!!!!
Hii all do not blindly follow, he is a great mentor. There is no doubt but 22:00 he explain tabulation method ,but neg variable is not used,a[index] will be contant at the for loop , output will be definitely wrong. This is the modified code. Pls check it. static int adjSumArray_Tabu(int n,int[] arr,int[] dp) { dp[0] = arr[0]; if(n>1) { dp[1] = Math.Max(arr[0], arr[1]); } for (int i= 2;i
In this tabulation approach we consider max by picking a[i]+dp[i-2], now you may ask we can also take a[i]+dp[i-1], why? because lets say dp[i-1] is made by not picking a[i-1] so you can consider dp[i-1] but there is no need as it is redundant because if dp[i-1] is max sum till index i-1 without considering nums[i-1], it means it definitely picked a[i-2](as all are positive numbers)so dp[i-2] will be same as dp[i-1] in that case.
This is just the 4th lecture, I struggle a little bit while writing recursive solution, but memoising it, and then tabulating it, and then space optimizing it has become so easier, i never thought dp would be fun. Thank you sir!
No need of if (i > 1), in space optimization. We can directly write like this, as prev2 is 0 anyways. int rob(vector& nums) { int n = nums.size(); int prev = nums[0]; int prev2 = 0; for(int index = 1; index < n; index++) { int rob = nums[index] + prev2; int notRob = 0 + prev; int curr = max(rob, notRob); prev2 = prev; prev = curr; } return prev; }
In space optimisation approach there is no need to check the condition as the index can not be negative and we have create a variable that is prev2 for index = -1
hands down the besttt ever video i have ever seen i solved this robber problem using kind of pattern but why i never understood how did it work ...but i always wanted to know how it works internally....but i have to say now that i hate that kind pattern orinted dp problem instead i love this memo and space idea.....Hats off!!!striver bhai❤
Understood!! Thank you for all the efforts in putting up such an amazing playlist! Really sparks my interest in DP, knowing the thought process behind solving every problem. Keep up the good work!
I need your support, and you can do that by giving me a like, and commenting "understood" if I was able to explain you.
Understood bro
Understood 🥺
Understood 👍👍
Understood
Understood😁
Understood Sir. At 3:50 min of the video I paused it and went to the recurrence playlist, then watch lecture no 6 & 7 thoroughly and then came here .Amazing session .Thank You Sir for helping us to improve our skills.
Thanks 😊
Believe me I have been trying to solve dp problems since 6 years and never came across this playlist. Amazing learning technique. This will surely help me in cracking interviews.
I got confused when you wrote f(ind) at 7:57. Immediately, the pop up rectified the mistake. It's amazing how much work has gone in these videos! I'm loving the playlist till now! Keep up the good work man. Your inputs to the community are huge and they will definitely return back to you in one way or another. Best wishes!
Thanks for this comment, I was confused and noticed only after you say!
I love it when you get so excited and start speaking your native language.
You are amazing striver
Today I had my Amazon interview and I got this exact questions and after completing the striver's dp series I was fully able to solve all the approaches and explain it to the interviewer so clearly and he was impressed by the way I explained the approaches and the time and space complexities! THANK YOU STRIVERRR!! You are the bestttt🎈
This is my 1St comment on this channel
Really he is explaining the thought process which should be come when we are solving problems
Instead of adding base case as if(ind
I was struggling with this basecase and was missing to apply the max method considering the arr[0] too. Thanks for commenting this out.
what an energy man....!!! ❤The way you teach make me fall in love with the programming .....!!
Initially I was not able to understand anything related to DSA. I thought that I am not for this. But when i started seeing your videos I found that what I was lacking was a good teacher who is able to understand such advance complex concept in matter of minutes in the best simple way possible. I would have never imagined myself solving hard level dsa questions without you. Thank you sir for all your efforts . Please continue teaching. We will be always with you. THank YoU.
This is indeed the best DP series. Thanks for providing such quality content for free. I'm really enjoying it.
The way you explain na, aisa lagta hai ki you yourself enjoy this, and that is why your basics are so clear. Keep it up. Google ka CEO banoge ek din.
@@utkarshsharma6650 app bi
US
So TRUE. Striver enjoys coding. Coding is Fun for many geeks.
Hats off to this guy whenever we discuss about dp, people just start with tabular method no one teaches how to apprach that, what is the intution behind that approach but this guy making the concepts crystal clear. Thank you so much bhaiya😇
what a content it's amazing . DP becomes easy for me till now because of you.
Thank you so much.
The energy while teaching is just awesome man even a sleepy head can understand the concept u teaches, Hats off!❤
I can find the recurrence relation of a problem and determine whether it is a dynamic programming problem by determining if there is any overlapping sub-problem. The interesting fact is that I have learned these from this playlist. Thanks a lot, bro.
I think we can write one more base case for index = 1. Like 0, when 1 is reached then it means element at 2 wasn't selected and we want to maximize sum so we can select either nums[0] or nums[1] so return max(nums[0], nums[1]) as we need to maximize sum. By doing so we can omit the line that is returning 0 when n < 0
Thanks Striver, Wonderful explanation!
I never had a habit of commenting. But the way you are teaching makes me enthusiatic towards dsa understood each and every concept following from array to dp was a long journey. It wasnt possible without .once again thank u bhai❤
ur teaching method is just awesome....no one in the entire TH-cam world has made such a best video on DSA. lots of love from my side.🤟🥰
Its good to watch good content for free.. I just finished recursion playlist and now watching DP. For me it is a hard topic, tabulation technique is most difficult but i hope i will get it by the end of this playlist. (NON-CS BACKGROUND)
Striver has to be the craziest guy, came here to get through placements ended up wanting to code for fun!!! Understood concept very well!!
Understood..You make learning fun :) I am done with my interviews but still don't want to miss learning any concept.This has never been me but all thanks to you :) You're indeed doing a great job!!!
Falling in love with programming ❤️ all credit goes to you ..the way you teach is just🔥🔥
Your enthusiasm and energy grabs my entire focus on the topic🔥🔥.. thank you for the series🙏🙏
"understood"
In space optimizations, it's better to initialise things like this:
int pre1 = nums[0];
int pre2 = nums[0];
int curr;
Just because this makes more sense.
bruh, prev2 needs to be 0 because also if the negative check is omitted it'll work fine.
"US"❤ the only channel which makes me understand all these problems so easily. Thankyou so much sir!!
thank u for this dp series. It's actually clearing my concepts.
bhaiya you are the best i mean i was confused with dp for so long time and this was becoming the only topic which I was afraid to cover but now my concepts are getting clear and thankyou so much for this series at this time since this will help me do goood in my internships thankyou bhaiya 🥰🤩
Kya haal hai khushi 😏
Man you are a genius when it comes to teaching!!
it was literally the best series . i am myself to able to code recursion problems now and its boosting my confidenece and also bhaiya the space optimisation part is just awesome yar
Understood buddy. As usual, great explanation. Get well soon too. Just a request. Need a little more clarity on how to identify whether to approach as a greedy algo or dynamic programming pattern just by looking at a problem.
Generically if u see greedy failing, switch to trying all cases by recursion. For this u need your brain to generate test cases and figure this out that greedy is failing.
As much as I can think if the data is sorted and have uniform difference between them then I think we can go with greedy else dp
Correct me if I am wrong plz
@@aakashagarwal146 not uniform but some sort of increasing difference
In coin change problem greedy works for 1,2,5,10,20.... becz difference is 1,3,5,10 which is in order and not overlapping
but in cases where difference is overlapping or not in any order like when coins are 2,3,6,7.
here greedy fails becz the difference is 1,3,1 which is overlapping
hope you got the idea
Bhaiya Codestudio platform is lagging many a times , could u please provide problem links of similar type that are available on gfg , leetcode , codeforces, codechef etc for practice
House robber problem on leetcode
BEST DP PLAYLIST EVER
Can we write base case for 1 if(n==1) return max(a[0], a[1])
yes but that is only if the size of the vector is more than 1
You explained so well, dp was to be hard topic for me but after watching your videos the thought just reversed. Keep going. Most hardworking man i ever seen.
Understood perfectly, It has been so easy now to convert recursive code to Memoization, Tabulation and then space optimization approach
Thanks A Lottt!!!!
UNDERSTOOD............Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Fully understood dada, your explanation is more than enough to write the actual code by ourselves!
The way you teach..omg!! I just love it❤
Thank you sir 🙏
Understood!!
@25:18 Intro to space optimisation🔥😂❤.Thank you very much. Crystal clear explanation❤🙏
Hii all do not blindly follow, he is a great mentor. There is no doubt but 22:00 he explain tabulation method ,but neg variable is not used,a[index] will be contant at the for loop , output will be definitely wrong.
This is the modified code. Pls check it.
static int adjSumArray_Tabu(int n,int[] arr,int[] dp)
{
dp[0] = arr[0];
if(n>1)
{
dp[1] = Math.Max(arr[0], arr[1]);
}
for (int i= 2;i
Sir.... You are legend... Only one word to describe you
The way he teaches is detailed and easy to understand. Thanks a lot!!!
UnderStood , u are literally teaching in very nice manner.
int rob(vector& nums) {
int n=nums.size();
int prev2=0;
int prev1=nums[0];
for(int i=1;i=2)
{
pick+=prev2;
}
int notpick=0+prev1;
int curr=max(pick,notpick);
prev2=prev1;
prev1=curr;
}
return prev1;
}
In this tabulation approach we consider max by picking a[i]+dp[i-2], now you may ask we can also take a[i]+dp[i-1], why? because lets say dp[i-1] is made by not picking a[i-1] so you can consider dp[i-1] but there is no need as it is redundant because if dp[i-1] is max sum till index i-1 without considering nums[i-1], it means it definitely picked a[i-2](as all are positive numbers)so dp[i-2] will be same as dp[i-1] in that case.
This is just the 4th lecture, I struggle a little bit while writing recursive solution, but memoising it, and then tabulating it, and then space optimizing it has become so easier, i never thought dp would be fun. Thank you sir!
No need of if (i > 1), in space optimization. We can directly write like this, as prev2 is 0 anyways.
int rob(vector& nums) {
int n = nums.size();
int prev = nums[0];
int prev2 = 0;
for(int index = 1; index < n; index++) {
int rob = nums[index] + prev2;
int notRob = 0 + prev;
int curr = max(rob, notRob);
prev2 = prev;
prev = curr;
}
return prev;
}
"US" what the heck man, that space optimization is just superbb. thankyou so much striver.
Great explanation Sir, You teach each and every concept with accuracy.Thanks a lot.
you are legend for dp playlist
In space optimisation approach there is no need to check the condition as the index can not be negative and we have create a variable that is prev2 for index = -1
Understood !!
I know you are striver but for us you are a saviour..!
Understood. I watched this question on some other youtube channel but this one was far better.
best teacher ever
hands down the besttt ever video i have ever seen i solved this robber problem using kind of pattern but why i never understood how did it work ...but i always wanted to know how it works internally....but i have to say now that i hate that kind pattern orinted dp problem instead i love this memo and space idea.....Hats off!!!striver bhai❤
your way of solving DP problems really helpful for me. Thanks a lot
Your explanation is amazing, and your enthusiasm.. contagious. Can't thank you enough man.
Understood bhaiya with so much clarity, Thank you so much for providing content like this. Thank you again bhaiya
"Understood". Another amazing lecture!!
incredible explaination striver
love babbar bhaiya of channel code help explains space optimization sir. He also explains it very well.
the space optimization is the so good , i feel so understood .
Understood and solved on my own, thank you striver for the amazing lectures!!!
Understand veryyy well
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n==0: return None
if n==1: return nums[0]
if n==2: return max(nums[0], nums[1])
dp = [-1]*n
dp[0] = nums[0]
dp[1] = max(nums[1], nums[0])
for i in range(2,n):
pick = nums[i] + dp[i-2]
notpick = 0 + dp[i-1]
dp[i] = max(pick, notpick)
return dp[n-1]
Finally i understood how recursion is working in this program 😊
understood,
very great video sir !!!
i was getting afraid from DP in vain , it seems to be quite easy and interesting to me !!
@@nitishaverma6557 Which college do u study
Understood sir! Thank you for these amazing lectures :)
Understood!! Thank you for all the efforts in putting up such an amazing playlist!
Really sparks my interest in DP, knowing the thought process behind solving every problem.
Keep up the good work!
with due respect, Love babbar also teaches space optimization, but your explanation is better.
Thank You Soo much Sir, I went for to much resourse to learn DP but your playlist is just awesome🙂.
"US"
Thanks a lot bhaiya was able to solve it by my own
Awesome explanation
I am a huge fan of yours. Please please do all data structures topic like Greedy,.....etc.
Excellent.....Amazing.....fabulous.........
Understood sir ji
Understood , now dp seems easy to me thank you so much sir 💙
Solution for : Maximum Sum of Non Adjacent Elements:
#include
#include
using namespace std;
// recursive
int helper(vector& nums, int index) {
if(index == 0) return nums[0];
if(index < 0) return 0;
int notTake = 0 + helper(nums, index - 1);
int take = nums[index] + helper(nums, index-2);
return max(take, notTake);
}
int rob(vector& nums) {
int size = nums.size();
return helper(nums, size-1);
}
// memoization
int helper(vector& nums, int index, vector& dp) {
if(index == 0) return nums[0];
if(index < 0) return 0;
if(dp[index] != -1) return dp[index];
int notTake = 0 + helper(nums, index - 1, dp);
int take = nums[index] + helper(nums, index-2, dp);
return dp[index] = max(take, notTake);
}
int rob(vector& nums) {
int size = nums.size();
vector dp(size, -1);
return helper(nums, size-1, dp);
}
// tabulation
int rob(vector& nums) {
int size = nums.size();
vector dp(size, 0);
dp[0] = nums[0];
for(int i=1;i 1) {
take += dp[i-2];
}
dp[i] = max(take, notTake);
}
return dp[size-1];
}
// Space Optimization
int rob(vector& nums) {
int size = nums.size();
int prev = nums[0], secondPrev = 0;
for(int i=1;i 1) {
take += secondPrev;
}
int curr = max(take, notTake);
secondPrev = prev;
prev = curr;
}
return prev;
}
Thankyou Bhaiya for this type of explaination , It helps me a Lot Lots ......... ❤ Understood
Really Amazing explanation I am able to understand each and every concept very clearly 😇😇
Solved it myself , thanku so much to make the dp concept easy
Understood!!Amazing Videos
us bhai. amazing lacture
Amazing Lecture!!!
thank you so much bhaiya for this amazing playlist
Understood: wonderful explanation! Thank you Sir!
Thanks a lot. You are awesome. Understood very well.
you really deserve a like
He teaches man❤
Understood! Thank You Sir!
understood bhaiya
Salute for your hard work
Understood sir❤
US. Great teaching.
Understood sir
Understood !!
btw I just wanna tell Dada and I are from the same college.
UNDERSTOOD
Understood !!!!! Thankyou so much Striver