What Is Dynamic Programming and How To Use It

*Dynamic Programming Tutorial*
This is a quick introduction to dynamic programming and how to use it. I'm going to use the Fibonacci sequence as the primary example.
Sample code is available in Jupyter Notebook and plain Python at: www.csdojo.io/dpcode
Keep in touch on Facebook: / entercsdojo
Support me on Patreon: / csdojo

[@CSDojo]

I missed putting a second argument (memo) at 6:16 when calling fib(). Sorry. Anyway, here’s an outline of this video: 0:00: Intro 0:38: What’s the Fibonacci sequence? 1:37: 3 steps for solving a problem with dynamic programming 2:21: Finding the n-th Fibonacci number with recursion 4:28: A memoized solution 6:37: A memoized solution - time complexity 9:24: A precursor to the bottom-up approach 10:45: A bottom-up approach 12:30: Demo with Python and Jupyter Notebook Sample code is available in Jupyter Notebook and plain Python at: www.csdojo.io/dpcode

[@therohitsahani]

CS Dojo I am very interested in technology and related of it. And if in the future I want to get a job at #Google so what should I have learned before getting into the #Google

[@nightlight3169]

Is python automatic able to store that big of a int? Because I try to find very big number in the fib seq but nothing in Java can Gould something that long and big

[@benjaminsteeth2966]

You don't deserve Google. Google deserves you.

[@Ahmad_here_1]

YK i have a question please reply.I am taking your python lectures already should i take your dynamic language lectures?

[@Rohitsingh2410]

Hey YK .. i am a beginner with algorithms and data structures can you refer me some good video tutorials and books on data structures and algorithms. Thanks

[@pguti778]

Thank you CS dojo !!! I've passed a job interview because of this!!! You're the best!!!

[@stard1758]

Are u serious?, can u explain to me what job exactly did u get and what they asked u exactly ? Thank u

[@kossklepht3843]

@@stard1758 Almost all the big companies are using dynamical programming problems during technical interviews.

[@viziopuzi9339]

@@rohitshekharsingh2579 right ! Kudos to being jerk of the year !

[@ayushraj6525]

@@rohitshekharsingh2579 Awww, Poor brain💩💩💩

[@tongpoo8985]

@@rohitshekharsingh2579 someone is bitter

[@TinOfBeans321]

You're great at explaining! I'm a final year comp sci student and have come across fib and dp countless times but this is the simplest and best example I've seen yet. Keep it up!

[@CSDojo]

Thank you!

[@RachitJain]

You should also checkout this video then goo.gl/StJCAq

[@maxim9280]

Well we had it in school. And I still don't consider myself good at programming

[@HarshPatel-iy5qe]

Hey buddy from which university you're pursuing?

[@raj_patel_43]

@@RachitJain hey bro, i am your subscriber, your are legend

[@doumkatekz]

Thank you! I'm a developer without a CS degree. Never really needed it but I'm trying to level up my skills and seeking out the things I've missed. Been doing it most of my life and I'm probably twice your age, never mind ego and pride, I'll learn where the learning is. Excellent video and explained very clearly.

[@CSDojo]

Thank you so much for saying that!

[@TjMulyadi]

Ditto here , Bro. I'm aLmost 40 but age doesnt matter when it comes to Learning. Learn from younger ppL never bother me a bit... hey one day our young friend here might Learn something from someone even younger.

[@jhguygih]

I have bacharel in System information which had very basic algorithms and now that Im 32 and studying those to improve my mind explodes in every video. Also he explains very well indeed.

[@HanifCarroll]

Same! I'm a bit older than the fresh grads at 28, but I'm self-taught and have been programming for 3 years now. Within the last couple of months I decided to start learning more about data structures and algorithms, and boy, it's incredible what it's done for my problem solving abilities. I feel so much quicker and more confident now. And it actually uncovered an interest in numbers that I didn't know was there!

[@onilbautista]

this is so nice! you go man!

[@nemousama4637]

Awesome video. I'm a professional software developer who has been programming for a decade, and I still found this video helpful to put a name to something I've been doing without thinking. Also, you have almost single-handedly erased my prejudice against KZbin videos as a medium for quickly conveying CS/programming concepts. You are concise, to the point, presentable, and easy to follow. You do not waffle or waste people's time with showboating. I will be recommending your channel from now on.

[@michaelw7769]

Well explained! One suggestion for your bottom up approach is that you don't need to use an array with size n to hold all the numbers, you just need 2 variables to hold the previous two numbers, and keep updating them when iterating.

[@igorthelight]

That's smart! ;-)

[@charan_75]

For anyone wondering how to do using two variables in bottom up approach. def fib(n): if n == 0 or n == 1: return n first = 1 second = 0 result = 0 for i in range(2,n+1): result = first+second second = first first = result return result

[@codewithsheikh2805]

If you just need result of nth Fibonacci but he is populating array.

[@coffeedude]

​@@codewithsheikh2805he is just returning the final result, not the array

[@Sant270]

using fib sequence to teach recursion and DP is a very bad idea

[@vidyaranyatj7306]

Smart, Humble and Simple. You're the best my man.

[@anoops7974]

i am a 3rd year computer science student , although i have already done with data structures and algorithms courses . i have never really felt understood . this video helped me so much , hope you will continue doing these to help students like me , i am definitely going to share your works on my class group . please never stop adding more videos , i am looking forward to all your upcoming videos . i love these so much , thanks a lot once again

[@vendels4154]

I must say, this is a very nicely done video, the example problem is simple enough to grasp the concepts for DP beginners like me, but also complex enough to demonstrate the usefulness of it and also impact of the different complexities. I have always had a hard time understanding recursive solutions (my brain just tends to get overwhelmed from it), but after this I actually feel I have a better understanding. Thank you for making this!

[@dhawalmajithia4959]

I keep coming back here for a refresher every time I have an interview scheduled. Love this

[@DadBodSwagGod]

I feel like an idiot. I never realized that Dynamic Programming wasn’t actually anything special. It’s just a few commonly used strategies for solving any given problem

[@sabah8312]

haha ... Same here

[@nadiequintero9981]

Well, you're not an idiot. You were just uninformed.

[@ayemaeyalit3354]

Is it just recursion or is it also something else?

[@DadBodSwagGod]

@@ayemaeyalit3354 It's basically the idea of the algorithm changing priorities and not looping through stuff it knows won't give it a result, preferably in a way where it was designed to eliminate those possibilities in as few operations as possible. That, as opposed to the basic thing of just looping through everything. You've almost definitely done it without knowing the word for it if you've taken at least a few years of computer science classes

[@MyFictionalChaos]

algorithms arent super advanced concepts. you have to remember the majority of computer science has existed in the past century

[@Elena-tj3so]

This is by far the clearest explanation of dynamic programming I've seen! It's a topic I keep having to relearn every now and then but I think I finally truly understand it now.

[@davidranney8723]

This is an excellent explanation. You chose a problem which is just complex enough to illustrate the technique. You methodically go through the steps and explain each step completely. I wish more tutorials were like this one. Well done!

[@domainxh]

I migrated from aerospace engineering background to cs roughly two years ago. I can code, but doesn't know much about cs fundamentals. I learned quite a bit watching your videos. Keep up the good work!

[@raghavendra2096]

I am following your data structures playlist and came across recursion where you mentioned dynamic programming and i came here. You are a great teacher with passion, that's what makes u separated from others. This is my opinion by seeing your videos. Sometimes some people teach some stuff which is also good but it might make you doubt yourself, here even though i have watched with just 50% focus (after a day long work) i could still understand. Thanks soo much for teaching us all for free, i feel grateful that we have internet and best teacher teaching it all for FREE!!!

[@mereel77]

Struggling to understand DP...this was a fresh perspective, really helped, thanks. The call-out to skip recursion and just fill in the table left to right is a game changer.

[@lynnguyen8652]

I've reviewed several DP resources, and none of them sit that well. Yours is the best and easiest to understand. I wish I started with your video. Would've saved so much time!

[@minhthinhhuynhle9103]

This is much better: kzbin.info/www/bejne/pXPXZmaPl7dsgc0

[@sakshijuyal9877]

The way he has explained is simply amazing....

[@di3g04]

Man, the best explanation in KZbin, I've been trying to better understand a topic for about an hour.

[@emmabarron6578]

That was fabulous. I'm in AP CSA right now, and I didn't think I would be able to find such amazing videos over coding on KZbin. I like to think I know a decent bit, but what you showed right there... it blew my mind. Even with my limited Python skills (the AP exam is in Java) I was totally able to follow. Those concepts were really neat, and your explanations were crystal-clear. Thank you so much!

[@canastrao]

You know how to teach people. It is really helpful.

[@VideoNOLA]

Wonderful and helpful example! Of course, as a mathematician, my first instinct is to Google "explicit function for nth term of Fibonacci sequence", which yields either the Binet formula, or the more succinct alternative F(n)=⌊φ^n/√5 + 1/2⌋, where φ=(1+√5)/2 is the so-called golden ratio. Most recursive functions can indeed be rendered explicitly, though it's not always obvious or easy how to accomplish this.

[@brieananichole]

You are my hero, the difference between the recursive approach vs the bottom up approach is incredible. Thanks for making these ideas so easy to understand!

[@hyrummoses1851]

I'm a sophomore in CS and was struggling to understand dynamic programming and how it differed from regular recursion. After watching this video it makes perfect sense and I can now implement it in my future programs. Thank you so much!

[@abraiyan7984]

This is mind-blowing! Thanks, Dojo.

[@kirtipurohit1237]

hey! I'm a first year student and I love programming alot. These topics aren't taught to us in college yet but my love for programming and computer science brings me here . Please make more videos with new concepts and tips for students who have just started programming !!! Thank you!

[@akankshasingh3075]

This is the best explanation of DP on KZbin. Have exam in 2 days and this really helped me in understanding basics. Thanks for this. Keep making more such videos.

[@nadamson14]

This is THE best DP video on KZbin! The example you use is very simple but you really helped me understand what this approach is all about

[@EDemircivi]

amazing explanation, thanks :) keep up the good work man!

[@jemyAirlines]

Cs dojo am learning here in Kenya and I find how you teach, quite suites me well, keep it up helping others like me....

[@kells9k]

that country and all the "people" there are disgusting

[@brianmuhia2955]

am also from kenya

[@seanmcgr3459]

With your explanation, it finally feels like I understand how dynamic programming works.

[@MaXxamillion00]

Really impressed with the video. I liked the way you presented code that you had already written, line by line, while explaining the code. It was really clear and not overwhelming. Thank you for making this!

[@roots6770]

After that make 10-12 videos giving more examples of it. That would be awesome 😃✌

[@savithak.6516]

Can you please cover the pattrens discussed in this course www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews?affiliate_id=5457430901161984

[@AkshayNehe_invincible]

Great explanations! Thanks for these awesome videos. Similar to the call stack overflow issue with the recursive solution, I was thinking about the extra memory utilization by the bottom-up approach. The presented solution uses about O(n) memory but in each iteration we only need to access 2 elements from the array so we can even implement this using constant space by storing only previous two values instead of all values from the start. So savings on both space and time 🙂

[@beltusnkwawir2908]

I have always believed simplicity is fundamental basis for explaining and understanding any complex concepts. You just proved that here. Thanks @CS Dojo explicit and easy to follow video

[@praveenchouhan6388]

the best explanation i have seen on DP till now which covers all aspects of DP - naive, memoized and bottomup, excellent work!!!!!!!!!!!!!!thanks

[@thawsitt]

You only need 2 variables to store the last 2 fib values. The following code has O(N) time complexity O(1) space complexity. def nth_fib(n): a = 0 b = 1 for i in range(n - 1): temp = a + b a = b b = temp return b

[@nekojackson9856]

The advantage of the video's style of memoization comes in when the same function is called multiple times. If the video's function has already calculated fib number N, and you now want to use it to compute fib M ≤ N, then the second function call just has to look up N in a pre-initialized array. That reduces computational complexity to O(1) for that second call

[@jaspersasa6868]

THANK YOU SO MUCH : well explained

[@PrasannDeshpande]

This is the first time ever that I have gone out of my way to like a video. Had to open another chrome with a personal Google account(the school account won't let me log in), find the video again, and like it. Needless to say, the video is just excellent!

[@chloem.872]

This was awesome, thank you so much. I'm a CS student starting a research assistant position in bioinformatics and this has helped prepare me for my job. Thank you!

[@pweddy1]

This just reinforced my feeling on recursion! When efficiency or memory usage is important, find a different solution! The bottom up approach was what I got out of analysis of algorithms 25 years ago! But people today don't seem to be taught that today?

[@momonga.]

Idk I just had my algorithm design final today and we had two DP problems that totally destroyed me 😭

[@mrhyperboss4204]

Really amazing I saw your channel when it was 10k now 137k with in a year congrats

[@arnabdas2967]

Me too

[@1ycx]

Now 700k

[@geekyprogrammer4831]

now 800k :O

[@klarnorbert]

879k :D

[@ahfadm4311]

923k :O

[@sahibjaspal1747]

Hey YK, You are really good at this. Thank you for taking out the time to create these videos. Please add in more DP problems as these are the hardest to understand and deal with. Cheers

[@Shingorani]

Excellent explanation. This is the best channel I've found for preparing for coding interviews!

[@ricardoorellana1168]

In the recursive calls of fib, you forgot to add the memo list, it should be: *result = fib(n-1, memo) + fib(n-2, memo)* Great video and explanation!

[@wangsherpa2801]

You are bit a confused friend. Watch the video again there're two functions one takes one argument and another one takes two.

[@nitinat3590]

@@wangsherpa2801 In the memoized solution when the recursive call is being made memo needs to be passed

[@Vens8]

That was just a pseudocode so it wasn't necessary. He did that during the demo of the actual code.

[@dipikamandal5334]

It's so simple. Thanks 😊 Please make more videos on dynamic programming.

[@jithinp8234]

😓😓😓simple....

[@taylormcneil2285]

This video was super helpful! The first time I saw dp, it was explained in a very complex way. This is so simple!

[@ethansodaro3945]

oh man...You literally nailed all that stuff in a few! A bigggggg time appreciation from me.

[@MASTERISHABH]

This is my solution for that question in Python which takes O(n) time with O(1) space. a, b = 0, 1 for _ in range(n): a, b = b, a + b return b PS: If you want to implement this in other languages, simply add a temp var when swapping a and b.

[@VivekYadav-ds8oz]

Well yeah that is the most common way of doing it. This example was really good in explaining dynamic programming because nobody is caught up in the solution, just the process.

[@somerandomguy000]

For fib, dynamic programming is the way to solve the problem we introduced ourselves when we went from the classic procedural to the recursive solution. And then bottom-up is just going back to procedural but adding an extra linear space complexity

[@jaylanlee945]

wasn't really the point of the video but since we're on it, you can also calculate the fibonacci number using the following formula: f(n) = (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5) this should have constant time complexity it's unreadable as fuck but whatever

[@ranjim]

@@jaylanlee945 yeah its a math way around

[@lesarXD]

you actually dont need a temp var: b += a a = b - a

[@cwagnello]

At about the 6:30 mark when talking about memoization the array never gets the values of fib(1) or fib(2). The way the code is set up it falls through and then returns fib(1) and fib(2) at the check for n == 1 or n == 2. The comparison at the end is a nice touch to teach about a potential drawback of a recursive solution.

[@cesarjom]

Your coding solutions (in all videos) are so well explained and in short time draw such insights into the overall algorithm. Thanks!

[@SuineXYT]

Thank you very much for your video. It was clearly explained, and much easier to understand than my college textbook. It took you 5 minutes to help me understand what I couldn't in a few hours of reading. Thanks!

[@pranavmishra9366]

lots of love from India brother, you are awesome in explaining things in detail. god, bless you.

[@abhinavkulkarni3427]

Thanks a ton csdojo for the tutorial you seems great in explaining the concept clearly 😃

[@kelseylally3463]

best description of dynamic programming ever, you are awesome

[@kitgary]

I have failed for many programming interviews as I don't know how to solve DP problems. This video is really life saving!!! Thank you so much!

[@therohitsahani]

I really like your videos very much I am thankful to you for helping me I always learn from your videos 👍👍☺

[@amishashukla1944]

Amazing video.....I love your videos. They are really helpful 😇.....Keep going, more power to you🎉✨💪🔥

[@Saurabh1337]

The way you explained this was delightful. Thank you!

[@stefanmendoza3537]

This made the concept so much clearer for me. Thanks for making this video!

[@shugabaabrahamwuta1833]

When you called fib(n-1), did you leave out the second argument memo on purpose?

[@sr_snehil]

That was not the original code... check the original code in the description. There, he made two different functions fib() and memo()

[@blackraven6049]

Can all DP algorithms be implemented with a bottom, up approach?

[@zihanqiao2850]

Clear explanation with an easy example. I really love the coding part and show the time difference!

[@ThunderBow98]

Bro I wish I found this video in March when we learned about dynamic programming. Great work I subscribed!

[@shourya436]

Sir,please take a question from codechef long challenges that are hard and based on dynamic programming,graphs,segment tree and more and please explain us that solutions...it would be very kind of you if you could help😃

[@simplifiedsolutions2297]

yes sir plz help

[@derpina615]

Yes agreed. Please pickup a harder example. Make this a series!

[@backslash8874]

Yup that would be great...

[@VivekSharma-nj3xd]

Yes!! Please do sir

[@AnandPandeyHere]

I post solutions of famous coding interview problems with proper explanation and codewalk. If anyone's interested can have a look at the videos. It will be really helpful for those preparing for placements.

[@echtcipher6682]

What is bottom up approach in programming?

[@RumeshEranga]

Wish your channel was available when I did my undergrads. Great stuff.

[@colorfulcodes]

I loved using Jupyter notebook. I need to start again. Thanks for this video!

[@lokeshsivakumar3927]

Help! as I am getting: Traceback (most recent call last): File "/Users/lokesh/Downloads/fibonacci.py", line 28, in fib_2(n,memo) File "/Users/lokesh/Downloads/fibonacci.py", line 15, in fib_2 if memo[n] is not None: IndexError: list index out of range

[@aashishmehtoliya5800]

just do n-1 in memo[n] in place of n , because array starts with index 0 and memo[n] covers 0 to n-1.

[@asdf-od5nm]

Make some programming video on your pc

[@JCho-pi5jz]

I rarely give compliments bc I always have something that bothers me about the video (i don't compliment tech videos) but WOW!!!! you're exceptional. your videos are AMAZING!!!! I have a physics degree went into DS/ML like most of us do and now I'm switching to CS. Your videos are so clear cut your speech is impeccable, perfect pace, sound and visual, and a nice flow. I can tell you did multiple takes or practice (if not that's REALLY impressive). combined with all you have a great knowledge base and present it *flawlessly*. Most of my interviews were things you covered and your videos are also the right amount of time. It's short enough to maintain interest and long enough to give you thoroughly. It's kind of a shame that people will only really tune in during interviews or when they are learning CS/DS. You structured it well with depth and breadth. You go into a great overview and then have videos that go into more specific which is WAY better than having one long video. I wish I saw these videos before just doing a bunch of leetcode problems. It's a great clean organized way of explaining the tools. I didn't know how many leetcode problems were enough but this is great! I used your info so much on interviews. It's so memorable and keeps my attention (I have ADHD so I'm really picky with videos). I'll definitely share your channel with people interviewing or anyone new to coding. If you decide to leave KZbin please keep these videos up. Also, you don't have that annoying "Aren't you amazed how smart I am?" arrogant vibe. You have a very humble, enthusiastic energy. Okay, this comment is way too long it's kind of creepy, but I'm a girl so how dangerous can I be? I just really wanted to let you know your videos are powerful and I really appreciate the time you take to edit them, it makes watching/learning so much easier. I know it's a lot of effort and it might not be obvious to people watching bc we're so focused on learning but I thought you should know it sets you apart.

[@JebBradwell]

That was really cool to see the evolution in developing out different approaches to solving the fib function! Thank you for this video!

[@umangchaudhary18]

Make videos for more complex programming questions (generally asked in interviews and technical online tests) which can be done by dynamic programming.

[@sriramsubramanian1291]

Hey yk, Great video again. One question, does the series not start from ZERO ?

[@alotlikees]

Your super power is turning abstract concepts into chunks that my brain can consume,.. programming alchemy. Gold!

[@SabbirAhmed-ve5rh]

I hope you reach 1M subscribers soon. You're doing an amazing work, man (thumbs up)!

[@NikhilSinghNeil]

didn't understand the part starting from 7:43 when the explanation for the second 'if' starts, explainig why it is n times

[@muhammadrahmatullahrahman1534]

it is n times because we don't need to call a recursion anymore since we already have the result of fib(n) inside the memo, that's why after the else block we do the operation to input result into memo

[@jjfrancay4544]

Hey YK! What is the best book/textbook to learn programing and basic CS?

[@aizazchaudary]

JJfrancay there's plenty of books you can find on Amazon but I highly recommend something like Codeacademy. Very good resource for basic cs.

[@gildardorosas8587]

CS is all about algorithms. The bible in CS is: Introduction to Algorithms www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844. Disclaimer this book is hard.

[@mustache2295]

Love the simple breakdown of this.

[@sarahy5991]

This video is everything. You've got awesome teaching skills. Thanks so much for taking the time to share your knowledge.

[@nickharalampopoulos]

Great explanation! Thanks. One error though. fib(3) = 2 because Fibonacci series starts with 0, 1 not 1,1. So it is 0, 1, 1, 2, 3, 5, 8 etc. One of the many sources www.mathsisfun.com/numbers/fibonacci-sequence.html

[@DarkLordAli95]

wow! this guy is adorable, brilliant, and not indian. subbed!!

[@curiosboi1681]

I am not an Indian but what's wrong with being an Indian? Stupidass

[@nogayful]

He means adorable and brilliant guys are indian

[@researchandbuild1751]

curios boi bad english skills and hard to understand

[@PACKERSFANSheshank]

that's not what he is saying he's saying that most programmers are indian, and he is not.

[@Kannan000]

Ha ha ... too many Indians in your 'brilliant and adorable' list? It's ok, we like this guy too!

[@MikayilAbdullayev]

Man, you asked and I'm letting you know in just one word: Fantastic.

[@sarfarazalam6077]

Great video! Easy to understand and made concepts crystal clear. Thank you!

[@dGuerra2462]

Big O notation please!!

[@thelavina]

David Vasquez google it

[@salmanfarooq8570]

aaaaah! "computation"! not competition! had me confused there

[@jayjw1]

Your videos are amazing man. You explain difficult processes easily and this is exactly what I needed at the moment

[@keritans]

Took Algorithms and read books about this and didn't know exactly what it was. Watched this video and now I'm an expert! Love the detailed explanations!

[@rahulr6723]

in the third last line, while calling "fib(n-1) and fib(n-2)", we would have to pass memo right. meaning "fib(n-1, memo) + fib(n-2, memo)" I think this code will show errror.

[@ivandrofly]

Yup

[@osacognitive3020]

Actually, wouldn't it need to be a global variable? Passing in memo wouldn't help us "remember" the result, would it?

[@osacognitive3020]

Never mind, just realized it depends on whether we are passing by value or passing by reference.

[@rahulr6723]

@@osacognitive3020 Once you declare a data structure globally you dont need to pass that every time. Here it will show error because the fib function takes 2 arguments but in the last 3rd line only one argument is passed.

[@danielchang2487]

Can anyone explain why 2n+1 for time complexity in 8:19 ? Let's say we run fib(3,memo), then there would be 3 times the function getting called ( fib(3), fib(2), fib(1) ), NOT 2n+1 = 7 ....

[@danielchang2487]

@Chris Blackwell still don't get it... :( can you give an example? is number of operations for fib(3,memo) = 2n+1 ?

[@joshking9537]

@@danielchang2487 Did you find out?

[@danielchang2487]

@@joshking9537 not yet..

[@metalore]

I noticed that too. I think it should be 2(n-2)+1 for n>1. The n-2 is because the first 2 indexes don't call the recursion.

[@arjun1194]

​@@danielchang2487 imgur.com/a/7x0yQiw

[@hugonavakopp]

Great work man, thank you very much for producing this material, it's really helpful. Keep up the good work!

[@KalimbaRlz]

the best explanation of dynamic programming I've ever seen

[@roshanmahtir940]

0:40 Fibonacci sequence starts with 0, 1 by the way.

[@xCwieCHRISx]

learned it the same way. F(n) = F(n-1) + F(n-2) and F(0)=F(1)=1 defined for natural numbers including 0 to be mathematical correct ^^

[@krupt5995]

Fibonacci is a sequence as its name defines so, thus that it is a function with a domain of the Natural Number's set, which means that what you are saying is true but in sequences, 0 is not usually used to avoid complexity. That's why often mathematicians use these elements S1, S2, S3...Sn.

[@lesterdale7276]

YK I love your channel, however I am always disappointed when everyone uses Fibonacci as an demonstration of dynamic programming. Could you please offer a different application of this programming technique

[@plouf1969]

I agree - there are a couple of examples that are not that complicated, but have real applications, and show the challenges met when doing dynamic programming.

[@nazli_muradova05]

I'm 9th grade student and i've started to learn python for 3 month, came across with using dp for solving eolymp tasks,this video helped me to understand the whole concept! Thank you!!!!!!!

[@Kokurorokuko]

The fact that the most efficient solution is so freaking simple is amazing.

[@sergey198]

You don't even need an array in your "bottom up solution"

[@YassineAbdulRahman]

can you calculate it on the fly without array?

[@sergey198]

@@YassineAbdulRahman of course, you only need two variables storing two previous values.

[@chiragasourabh6044]

Yeah exactly .. instead of filling up an array with n number of items u can use two variables storing previous two states and on every iteration update them . As temp = v1 , v1=v2 ,v2+=temp

[@MrNettoon]

@@chiragasourabh6044 That's exactly what i thought but its O(n) is bigger

[@mohammedfaour4136]

if an if-statement is before the for loop stating the if bottom_up[n] exists then i can cut the time because i can return the value instanty without entering the loop , this is useful if i have more than one call for the function, most useful in competitive programming

[@MegaMazenko]

Your code for the memoization solution is incorrect. You have result = fib(n-1) + fib(n-2), where you should have result = fib(n-1, memo) + fib(n-2, memo)

[@rohanshah7446]

Mazen Abusharkh isn't it simply better to declare memo as global and never pass it...?

[@MegaMazenko]

Rohan Shah, at 6:55 YK has else: result = fib(n-1) + fib(n-2) where his function is defined as def fib(n, memo): And yes, it is better to declare it globally and never have to pass it as a function arg

[@varesz9311]

Mazen Abusharkh checked the comments only to see if anyone else recognized it :D

[@kenhaley4]

The actual code at 12:37 is correct. Also, passing the array as an argument is no big deal if it's passed by reference. Some people argue against the use of globals wherever possible.

[@namlehai2737]

Not making everything global is a good habit. But in this case its ok

[@dvmibm]

It took me o(1) to subscribe to this amazing channel. Hands down the best dynamic programming explanation I've ever seen.

[@jungwoojeong3143]

Learning about Dynamic Programming right now and your video really helped me understand the elements of it and differences among them ! Thank you !