DP 1. Introduction to Dynamic Programming | Memoization | Tabulation | Space Optimization Techniques

Lecture Notes: takeuforward.org/data-structu...
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Pre-req for this Series: • Re 1. Introduction to ...
Full Playlist: • Striver's Dynamic Prog...
In this video, we have discussed what is memoization, what is tabulation, what is space optimisation with the classic Fibonacci problem. You might feel that this question has been done by you, but I will still urge you to watch this till the end because this is going to teach you a bunch of stuff.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward

Пікірлер: 3 100

  • @takeUforward
    @takeUforward2 жыл бұрын

    The notes are added to the description :) Keeping the blackboard size as it is because I don't wanna stretch it and lose over quality. Cannot upload more than 1 video daily, because I have a full-time job, and it takes 3-4 hours per video, including editing and all.

  • @cypher7536

    @cypher7536

    2 жыл бұрын

    Best best best!!!!!! ❤️❤️

  • @user-cg5jo2uy3f

    @user-cg5jo2uy3f

    2 жыл бұрын

    Thanks for making these videos. It's astonishing that you can run your channel in such scale when having another full-time job!

  • @PriyanshuSingh-hc3bf

    @PriyanshuSingh-hc3bf

    2 жыл бұрын

    Please increase the font size😶‍🌫😇

  • @TonyDUsopp

    @TonyDUsopp

    2 жыл бұрын

    @@coding8000 you'll give the editor salary ?

  • @akshitmangotra5370

    @akshitmangotra5370

    Жыл бұрын

    Understood. And thanks for the video ❤️. It's pro explanation

  • @utkarshyadav3401
    @utkarshyadav34012 жыл бұрын

    Years ahead !!! Striver would be going into history as legend for all IT students!!!! 🙏🙏🙏🙏🙏🙏

  • @iamnoob7593

    @iamnoob7593

    6 ай бұрын

    indeed!

  • @ranveerkumar3532
    @ranveerkumar35328 ай бұрын

    love the energy you have put in the entire video. it motivates me to watch 2,3 more lecture in one go.

  • @arunimaaa
    @arunimaaa6 ай бұрын

    My take from the video: 1. Recursion: each function calls give rise to 2 more: therefore O(2^n) 2. Memoization: stores in an array: O(n) Subproblem results are stored in an array, ensuring that each subproblem is solved only once. 3. Tabulation: iterative approach and takes O(n) subproblems from the smallest to the largest. RECURSION: Top down: We start from answer, go to the base case and then go back MEMOIZATION: TOP DOWN: avoids redundant calls done in recursion reducing time complexity TABULATION IS: Bottom up: We start from the base case and we try to go to the required answer

  • @raghavjoshi7236

    @raghavjoshi7236

    2 ай бұрын

    Thank u

  • @yadneshkhode3091
    @yadneshkhode30912 жыл бұрын

    Thank you for not forgetting us after joining google

  • @shashanksharma7747

    @shashanksharma7747

    2 жыл бұрын

    @@vivekshah3995 😂😂🔥

  • @sachinjuneja2405

    @sachinjuneja2405

    2 жыл бұрын

    Same feeling

  • @democratcobra

    @democratcobra

    2 жыл бұрын

    He is the LION. Lion 🦁🦁🦁 never forget !!!

  • @ShyamalDas-kd5vt

    @ShyamalDas-kd5vt

    2 жыл бұрын

    He born to do multitasking 🤩❤️

  • @rishav144

    @rishav144

    2 жыл бұрын

    @@vivekshah3995 yes 😂

  • @shivangisingh1988
    @shivangisingh19882 жыл бұрын

    I am blown away with the quality of the content and especially the optimization of space complexity at the end ...Literally nobody started DP with this clarity and precision....More power to you striver

  • @SwatiSingh-ys6hm
    @SwatiSingh-ys6hm9 ай бұрын

    Finally starting with DP series that i had been putting off for a long time...A wonderful lecture by striver as always. You are truly the best. Words are not enough to express my gratitude for your videos. You have made several difficult topics easy for me. I bet this one is going to be just as wonderful. Hopefully i can master this topic too by the end of your playlist. Oh forgot ..."UNDERSTOOD !!"

  • @ritikshandilya7075
    @ritikshandilya70752 ай бұрын

    @Striver I am wising I started following your content 2 years back , seriously its a goldmine . Thanks for all what you do for tech community for free.

  • @bibs24
    @bibs242 жыл бұрын

    I am not a master of recursion but i completely understood the whole lecture and enjoyed it! This is my first dp video that I watched and I am totally comfortable with it Thanks striver bro❤️

  • @yashhokte1020

    @yashhokte1020

    Жыл бұрын

    Agreed bro 🔥

  • @spytonic4171
    @spytonic41712 жыл бұрын

    This guy is going to revolutionize the entire Indian coding community with his simple and clear explanations of very hard topics thanks for the videos and notes and everything they are very helpful

  • @harshverma5873
    @harshverma587311 ай бұрын

    You're one of the most positive guy, Striver. I instantly start to feel motivated when I get across your videos.

  • @Zomb-zj4ip
    @Zomb-zj4ipАй бұрын

    understood. I cannot believe such quality content is for free, you are amazing

  • @vamshipaidimarri983
    @vamshipaidimarri983 Жыл бұрын

    I have started very late with DP Series but I am speechless after the video. Fibonacci looks like basic stuff for everyone but the way you have curated it using Memoization, Tabulation and Optimized (No extra space) deep rooted in my mind ("Understood"). Hats off brother!!! This gives me more energy and confidence to complete DP Series.

  • @tg62672
    @tg62672 Жыл бұрын

    The energy this guys put in videos is just awesome

  • @kaushiksen2190
    @kaushiksen21907 ай бұрын

    Thank You So much dada. Just got started with this amazing DP series. I manifest to have improved in DP, Graph, Tree, my DSA skills, my CP skills and work at a top product based company in the next couple of months. Thank You Striver, Thank You Universe, I am very grateful

  • @sai-mu9hj
    @sai-mu9hj4 ай бұрын

    the videos of dp series are good,you will fall in love with the first video itself

  • @amanwarudkar9913
    @amanwarudkar99132 жыл бұрын

    The way you teach stuffs by deep dive into it is amazing man... It's easy to understand what you teach because the way you teach. Hats off to your hardwork and dedication!!!

  • @tusharnain6652
    @tusharnain66522 жыл бұрын

    I am learning first time "dp" and I understood whatever you taught . Thank you striver bhai ❤️

  • @RakshithVrishab-ht8vk
    @RakshithVrishab-ht8vk8 ай бұрын

    Great Explanation! Huge Respect to you Striver Raj. and of course, "Understood"

  • @vishious14
    @vishious148 ай бұрын

    Loved the way you related everything to recurrence relation.

  • @kapilpatel9379
    @kapilpatel93792 жыл бұрын

    Understood a lot of this even without studying your recursion series, now will go and watch the recursion series

  • @bhaswatiroy1433
    @bhaswatiroy14332 жыл бұрын

    Not "just understood" but a different level of understanding. Hats Off !!!!!!

  • @aryansirohi8334
    @aryansirohi83346 ай бұрын

    I have always been scared of DP . But this video is Great . I understand DP in One video. God Bless You Man. ❤

  • @sanzayy
    @sanzayy6 ай бұрын

    Thanks brother ... for removing the fear of dp..... very well explained basics,,,

  • @ankitadas5833
    @ankitadas58332 жыл бұрын

    What A energy ⚡ level You have! And You explained everything such a detail.. When You throwing your lecture it seems like you are into it. That's why the Lecture is best in KZread. Thank you so much!

  • @falgunitagadkar4097
    @falgunitagadkar4097 Жыл бұрын

    Your energy while you speak is just amazing and ofc no doubt the best content!!! Hats off to you Striver!✌

  • @_ABHISHEKKUMAR-ep4zj

    @_ABHISHEKKUMAR-ep4zj

    Жыл бұрын

    ++

  • @user-xn5wu1ez4p
    @user-xn5wu1ez4p7 ай бұрын

    DP journey is about to start. Excited.

  • @pavanim6258
    @pavanim6258 Жыл бұрын

    Thanks a ton @takeUforward for ur awesome series and very organised playlists. The way u explain n the way its documented in the website is really superb.

  • @adarshanku7988
    @adarshanku79882 жыл бұрын

    I have finally started after procrastinating for such a long time and now i feel why didn't i started earlier, because after the very first lecture, i have got addicted to this. And this energy our STRIVER has.......ohh god he is really the Virat Kohli of programming world. And hell yeah UNDERSTOOD !!! You are really an inspiration for me. LOVE and RESPECT

  • @harshitaSharmaE
    @harshitaSharmaE2 жыл бұрын

    Omg raj!!! The amount of energy with which you delivered is really appreciated even a person will wake up from sleep😂😂 and most of people including me has already solved this problem but I was unaware of tabulation and space optimization... I was that involved in the lecture ki pata nahi chala kab 30 mins hogaye. Thank you raj for this amazing series definitely going to follow this

  • @aswinpradeep1287
    @aswinpradeep12873 ай бұрын

    So glad i came across your channel.

  • @quickturns76
    @quickturns765 ай бұрын

    your works are absolutely appreciable ,thank you so much sir!

  • @rishabhkalra9505
    @rishabhkalra95052 жыл бұрын

    thanks Raj for this. I have always been scared of DP like a lot of people. I hope this really helps me to improve myself in DP. God bless you man.

  • @AbhinavSingh-up7bl
    @AbhinavSingh-up7bl Жыл бұрын

    brother #Striver Date 17/06/23 I start watching your video at night 2 Am and now it is 6:30 Am feeling very sleepy but the ( energy + enthusiasm ) you are showcasing in this video make me motivate to watch more 2 and 3 videos , Really nice content with great knowledge

  • @iamnoob7593

    @iamnoob7593

    6 ай бұрын

    Also dont compromise sleep , Its important. All the best!!

  • @AbhinavSingh-up7bl

    @AbhinavSingh-up7bl

    6 ай бұрын

    @@iamnoob7593 yes

  • @clumsyshots5558

    @clumsyshots5558

    5 ай бұрын

    Us Moment!

  • @Someone-df7tj

    @Someone-df7tj

    Ай бұрын

    how is ur progress going

  • @saurabhgoel8191
    @saurabhgoel81916 ай бұрын

    Thanks man! Your videos really makes everything easy to understand moreover the program Dry run also helps understanding the approach behind it.

  • @prasangsayzzhii
    @prasangsayzzhii7 күн бұрын

    Understood. Your videos are amazing man.

  • @veerpratapsinghrathore7610
    @veerpratapsinghrathore7610 Жыл бұрын

    Nothing can be better than this; I understood the whole thing, and by the time you optimised that space complexity to a complexity of 1, I was totally gone, like, "Man, this person is just out of this world." Thank you, Bhaiya, for this wonderful explanation.

  • @anikethdeshpande8336
    @anikethdeshpande8336 Жыл бұрын

    i have learnt graphs from your graphs series, it was amazing , helped me understand the main concepts excited about DP !

  • @harikeshkumarsharma9834
    @harikeshkumarsharma98343 ай бұрын

    Nothing better than this SIR ...... Thank you so much SIR 🤟🤟🤟

  • @user-ei4sc8qb2q
    @user-ei4sc8qb2q Жыл бұрын

    excellent teaching and the energy of striver's teaching is insane

  • @RavinderSingh-qb4xi
    @RavinderSingh-qb4xi2 жыл бұрын

    Hope someday I'd have good problem solving skills like you ❤️.

  • @dhruvgupta2634
    @dhruvgupta2634Ай бұрын

    Understood. Amazingly Explained 🌟

  • @prabhakaran5542
    @prabhakaran55428 ай бұрын

    Understood Bro! Heartful Thanks for your effort!

  • @stankafan6688
    @stankafan66882 жыл бұрын

    you are vardaan for IT students. Thank you God for sending a teacher like you. 🙏😇❤

  • @aadityaburujwale8683
    @aadityaburujwale86832 жыл бұрын

    What a teaching bro! Amazing confidence and teaching like you have never seen before., Thanx for the series.

  • @SelvaArumugam-xq5mf
    @SelvaArumugam-xq5mf7 ай бұрын

    I understood its like a piece of cake walk and mastered your recursion playlist which made me recursion look very easy

  • @ankit-jangid
    @ankit-jangid4 ай бұрын

    UNDERSTOOD . .thanks for helping out community!!

  • @asmitmohan8253
    @asmitmohan82532 жыл бұрын

    Most Awaited Series Of DP Thank You Striver for all DSA Playlist Uploaded Till Now.🙌

  • @akshanshkumar4794
    @akshanshkumar4794 Жыл бұрын

    I am learning first time D.P and I understood whatever you taught . Thank you striver bhai ,your explanation really makes every topic so easy

  • @stith_pragya
    @stith_pragya7 ай бұрын

    Understood......Thanks a lot Striver Bhaiya.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

  • @nishithiyer
    @nishithiyer19 күн бұрын

    Understood! Brilliant videos and playlists. ♥ur work and you are such an inspiration to us all.

  • @piyushsaxena6243
    @piyushsaxena62432 жыл бұрын

    understood all the concepts, so easy to grasp as u teach so good , thanks for these lectures bhaiya

  • @keshav_k_0793
    @keshav_k_0793 Жыл бұрын

    STEP1 Create a dp[n+1] array initialized to -1. STEP2 Whenever we want to find the answer of a particular value (say n), we first check whether the answer is already calculated using the dp array(i.e dp[n]!= -1 ). If yes, simply return the value from the dp array. STEP3 If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[n] to the solution we get.

  • @suchithkumargm

    @suchithkumargm

    10 ай бұрын

    please pin this comment...its very useful

  • @SamPrakashM
    @SamPrakashM7 ай бұрын

    your explanation was exordinary .. Thank you for the explanation

  • @saavysisters
    @saavysisters2 ай бұрын

    understoodddd , tomorrow i have a technical round interview, literally i am watching this today ,so much thank you striverrrr always a big fannnnnnn

  • @sparshsharma6068
    @sparshsharma60682 жыл бұрын

    A suggestion for those who are learning live, keep the live chat hiddden until and unless it is necessary. This series will be lit! 🔥and yes liked shared and understood

  • @mihiradarsh7604
    @mihiradarsh76042 жыл бұрын

    Yooooo Let's goo, Finally👏👏 Understood, the best part is the optimization of the space complexity which you explained✌✌

  • @adityapatil1245
    @adityapatil1245 Жыл бұрын

    Understood…Thnks a lot for this series and really appreciate the efforts u are putting in for this series!

  • @everythingabout3479
    @everythingabout34794 күн бұрын

    What a energy sir . Best explanation ever

  • @bipul07_
    @bipul07_ Жыл бұрын

    Understood.. This is my first video of dp that I watched and really understood in very easy way.. Striver, you are gonna rule in future like SRK..

  • @dharmeshpoladiya9047
    @dharmeshpoladiya90472 жыл бұрын

    Understood 💯💯 Great Explanation. Thank you very much for all you efforts🔥🔥

  • @AmanPandey-bd1sj
    @AmanPandey-bd1sjАй бұрын

    Understand🎉 It's the best playlist ever

  • @mahindev1112
    @mahindev11127 күн бұрын

    Thank you so much for amazing and usefull content!

  • @jayantmishra6897
    @jayantmishra6897 Жыл бұрын

    this man is helping more than thousand of students at free of cost.the content provided by him is better than any paid course and the topics covered by him are very tough but the way he explains solution are extraordinary.

  • @amaanullah13

    @amaanullah13

    Жыл бұрын

    really?

  • @datkumar1024
    @datkumar10242 жыл бұрын

    Great Playlists! Please add Time-stamps as it makes it easier to jump to required parts

  • @Sanjana-nl1si
    @Sanjana-nl1si2 ай бұрын

    Understood Bhai! Amazing Explanation 🔥

  • @NirmalyaMusicOfficial
    @NirmalyaMusicOfficial14 күн бұрын

    Understood completely in detail 💯

  • @anmolverma2911
    @anmolverma29112 жыл бұрын

    Small Correction✅-> At 22:05 Fibonacci DP code is correct, but at the base condition i.e. if(n it should be if(n

  • @Vadya-nq8mg
    @Vadya-nq8mg2 ай бұрын

    Bro don't scream at me, I am afraid xD

  • @user-el6hv6em7m
    @user-el6hv6em7m23 күн бұрын

    understood, thanks a lot for this amazing series...

  • @studynewthings1727
    @studynewthings172710 ай бұрын

    Thankyou STIVER, I understood.

  • @Mohini-rt4wu
    @Mohini-rt4wu3 ай бұрын

    DP is very fancy word even after having 10yrs of experience I wasn't sure what is DP, you explained it really well. Thanks.

  • @sauravfarkade7032
    @sauravfarkade7032 Жыл бұрын

    No one can beat the Energy level of striver while he teaches any concept🤩

  • @kalashpatil2486

    @kalashpatil2486

    Жыл бұрын

    ho na

  • @artofwrick
    @artofwrick11 ай бұрын

    I'm already feeling motivated. Thanks for all these. ❤

  • @vigneshkannak2133
    @vigneshkannak21332 ай бұрын

    you are the best man! keep it up!

  • @snehilsinha4689
    @snehilsinha46892 жыл бұрын

    I think there's a small bug in the space optimized code. For n=0, the output will be 1,instead of 0, as prev is storing 1. Hence, we should write a seperate if check for n=0. Rest all looks good. The final code should look like -> class Solution { public: void fib(int n) { if(n==0){ cout

  • @Jason-qm8mu

    @Jason-qm8mu

    Жыл бұрын

    I didn't get it bro ,can we connect I'd ur on LinkedIn

  • @yathdixit

    @yathdixit

    6 ай бұрын

    @@Jason-qm8mu he is trying to say if we calculate the value of f(0), it will give output as 1 because prev is 1, and output is prev + prev2. He just added a condition of n == 0.

  • @agrawalhimanshu
    @agrawalhimanshu2 жыл бұрын

    First Comment on the amazing Series of DP ❤️🔥

  • @aps8874
    @aps88742 ай бұрын

    Thank you so much for this amazing playlist.💙

  • @aps8874

    @aps8874

    2 ай бұрын

    For my future self, let's see whether I am able to complete this by June 21, considering 2problems/day :)

  • @vibhavsharma2724
    @vibhavsharma27242 ай бұрын

    I "understood" like never before. Thanks to striver.

  • @nishant3904
    @nishant3904 Жыл бұрын

    Just AWESOME! Never thought such a simple problem can be solved in so many ways and with such optimization, why do our teachers never talk about these things?

  • @2KHuman

    @2KHuman

    Жыл бұрын

    Because Professor don't know this concepts and through School & College Faculties we are gaining only Basic Knowledge of any subject 😑

  • @codewithme6499
    @codewithme64992 жыл бұрын

    Thank you for tbe efforts.can u please explain java code as well😊 "Understood"

  • @takeUforward

    @takeUforward

    2 жыл бұрын

    Added in notes, its almost similar. Not a big diff.

  • @manojkr2362
    @manojkr23629 ай бұрын

    watching dynamic programming playlist second time ,let's do this shift and let me crack my interview, i have already got placed , and cleared first 2 rounds in ZOHO company with my 40% skills in DSA, now i have to level up my skills to next level , to this i have to complete this play list let's do this

  • @125_neeladityaghosh2
    @125_neeladityaghosh2Ай бұрын

    Thank You so much Sir 😃...Your explanation cleared all my doubts

  • @miragranger4685
    @miragranger46852 жыл бұрын

    Understood! Thank you Striver :) #include using namespace std; //Top-down approach int FibonacciMemoized(int n, vector & memo){ if(n

  • @shivamehta6537
    @shivamehta65372 жыл бұрын

    Please upload at least 2 videos per day if already recorded🙏🙏 btw loving your teaching

  • @takeUforward

    @takeUforward

    2 жыл бұрын

    Sorry bro, full time job :(

  • @lucifergaming2111
    @lucifergaming21118 ай бұрын

    Understood!! Thanks a lot, sir.

  • @adebisisheriff159
    @adebisisheriff1597 ай бұрын

    Thanks so much Striver.... Understood!

  • @dipakpatil4370
    @dipakpatil43702 жыл бұрын

    the best course ever, one small request brother if possible add timestamp's

  • @soujitd

    @soujitd

    2 жыл бұрын

    Yeah it'll be reallu helpful

  • @manasvinsharma1740
    @manasvinsharma17402 жыл бұрын

    Please take some variations also other than standard dp problems

  • @rox_official9407

    @rox_official9407

    2 жыл бұрын

    Yess sir

  • @raviashwin1157

    @raviashwin1157

    2 жыл бұрын

    @@rox_official9407 yes something different from Aditya Verma dp series

  • @rox_official9407

    @rox_official9407

    2 жыл бұрын

    @@raviashwin1157 btw he was my clg alumni

  • @rox_official9407

    @rox_official9407

    2 жыл бұрын

    @@raviashwin1157 bhai me Aditya verma ka dekhu kya phele ? Ya sirf yahi dekhunga to kam ho jaega

  • @raviashwin1157

    @raviashwin1157

    2 жыл бұрын

    @@rox_official9407 Dekh le bhai time hai to 2x me bhi ho jayega aaram se

  • @msanthosh3241
    @msanthosh32414 ай бұрын

    1 of the Best channel (CODING)

  • @ronaksiddhpura07
    @ronaksiddhpura076 ай бұрын

    I was Understood concept very well.

  • @_unblemished_soul_581
    @_unblemished_soul_5815 ай бұрын

    Previously I scared only by taking the name of dsa, now I feel that I can also do it. All thanks to you striver bhaiya.

  • @user-up2di5mm1q
    @user-up2di5mm1q9 ай бұрын

    Really appreciated your effort!

  • @AnushkaGupta-t8n
    @AnushkaGupta-t8n28 күн бұрын

    understood sir-great video

  • @NiteenChougula-fs9ij
    @NiteenChougula-fs9ij Жыл бұрын

    Hats off to you Striver!✌ Your dedication and hard work really show in your content. I'm truly impressed! Keep up the fantastic work.

  • @aryanatri9904
    @aryanatri99048 ай бұрын

    understood!! and congratulations on ur promotion😇

  • @awsproject7299
    @awsproject7299 Жыл бұрын

    Thank you. It was the best lecture, I ever seen.

  • @nikunjsoni123
    @nikunjsoni1233 ай бұрын

    I understood DP finally!!

  • @praveenrajagopal9161
    @praveenrajagopal91614 ай бұрын

    Good work brother!

  • @amritatiwary.
    @amritatiwary.Ай бұрын

    Understood very well 🎉