What Is Dynamic Programming and How To Use It
Вставка
- Опубліковано 12 гру 2017
- *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
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
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
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
You don't deserve Google. Google deserves you.
YK i have a question please reply.I am taking your python lectures already should i take your dynamic language lectures?
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
Thank you CS dojo !!! I've passed a job interview because of this!!! You're the best!!!
Are u serious?, can u explain to me what job exactly did u get and what they asked u exactly ? Thank u
@@stard1758 Almost all the big companies are using dynamical programming problems during technical interviews.
@@rohitshekharsingh2579 right ! Kudos to being jerk of the year !
@@rohitshekharsingh2579 Awww, Poor brain💩💩💩
@@rohitshekharsingh2579 someone is bitter
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.
That's smart! ;-)
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
If you just need result of nth Fibonacci but he is populating array.
@@codewithsheikh2805he is just returning the final result, not the array
using fib sequence to teach recursion and DP is a very bad idea
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.
Thank you so much for saying that!
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.
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.
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!
this is so nice! you go man!
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
haha ... Same here
Well, you're not an idiot. You were just uninformed.
Is it just recursion or is it also something else?
@@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
algorithms arent super advanced concepts. you have to remember the majority of computer science has existed in the past century
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!
Thank you!
You should also checkout this video then goo.gl/StJCAq
Well we had it in school. And I still don't consider myself good at programming
Hey buddy from which university you're pursuing?
@@RachitJain hey bro, i am your subscriber, your are legend
Smart, Humble and Simple. You're the best my man.
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!
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.
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 UA-cam 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.
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
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!!!
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.
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!
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!
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!
I keep coming back here for a refresher every time I have an interview scheduled. Love this
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
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
This is mind-blowing! Thanks, Dojo.
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!
Man, the best explanation in UA-cam, I've been trying to better understand a topic for about an hour.
The way he has explained is simply amazing....
You know how to teach people. It is really helpful.
This is THE best DP video on UA-cam! The example you use is very simple but you really helped me understand what this approach is all about
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!
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.
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!
This is much better: ua-cam.com/video/oBt53YbR9Kk/v-deo.html
the best explanation i have seen on DP till now which covers all aspects of DP - naive, memoized and bottomup, excellent work!!!!!!!!!!!!!!thanks
This is the best explanation of DP on UA-cam. Have exam in 2 days and this really helped me in understanding basics. Thanks for this. Keep making more such videos.
Cs dojo am learning here in Kenya and I find how you teach, quite suites me well, keep it up helping others like me....
that country and all the "people" there are disgusting
am also from kenya
amazing explanation, thanks :) keep up the good work man!
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
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!
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 🙂
THANK YOU SO MUCH : well explained
Your coding solutions (in all videos) are so well explained and in short time draw such insights into the overall algorithm. Thanks!
With your explanation, it finally feels like I understand how dynamic programming works.
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!
After that make 10-12 videos giving more examples of it. That would be awesome 😃✌
Can you please cover the pattrens discussed in this course www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews?affiliate_id=5457430901161984
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!
This video was super helpful! The first time I saw dp, it was explained in a very complex way. This is so simple!
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.
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.
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
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
@@jaylanlee945 yeah its a math way around
you actually dont need a temp var:
b += a
a = b - a
Really amazing I saw your channel when it was 10k now 137k with in a year congrats
Me too
Now 700k
now 800k :O
879k :D
923k :O
The way you explained this was delightful. Thank you!
This was a great quick intro to dynamic programming! I feel like I'm prepped with enough basic understanding/questions to go into my upcoming lecture with curiosity instead of fear :) thank you!
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?
Idk I just had my algorithm design final today and we had two DP problems that totally destroyed me 😭
It's so simple. Thanks 😊
Please make more videos on dynamic programming.
😓😓😓simple....
This made the concept so much clearer for me. Thanks for making this video!
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
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!
You are bit a confused friend. Watch the video again there're two functions one takes one argument and another one takes two.
@@wangsherpa2801 In the memoized solution when the recursive call is being made memo needs to be passed
That was just a pseudocode so it wasn't necessary. He did that during the demo of the actual code.
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.
Clear explanation with an easy example. I really love the coding part and show the time difference!
oh man...You literally nailed all that stuff in a few! A bigggggg time appreciation from me.
Thanks a ton csdojo for the tutorial you seems great in explaining the concept clearly 😃
lots of love from India brother, you are awesome in explaining things in detail. god, bless you.
That was really cool to see the evolution in developing out different approaches to solving the fib function! Thank you for this video!
Learning about Dynamic Programming right now and your video really helped me understand the elements of it and differences among them ! Thank you !
I really like your videos very much I am thankful to you for helping me I always learn from your videos 👍👍☺
Amazing video.....I love your videos. They are really helpful 😇.....Keep going, more power to you🎉✨💪🔥
best description of dynamic programming ever, you are awesome
Excellent explanation. This is the best channel I've found for preparing for coding interviews!
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😃
yes sir plz help
Yes agreed. Please pickup a harder example. Make this a series!
Yup that would be great...
Yes!! Please do sir
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.
Can all DP algorithms be implemented with a bottom, up approach?
I loved using Jupyter notebook. I need to start again. Thanks for this video!
I was so confused reading the university notes on DP. But now after this video, it all makes so much more sense. I've learned a few algorithms using DP but it's mostly because I understood the logic somehow, but as for DP, I didn't try to understand that particular concept much. Now I feel more confident about it. Thanks a lot!
Make videos for more complex programming questions (generally asked in interviews and technical online tests) which can be done by dynamic programming.
Hey yk, Great video again. One question, does the series not start from ZERO ?
fabulous video - thank you! loved the jupyter notebook example at the end that proves the value of the bottoms up approach
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!
wow! this guy is adorable, brilliant, and not indian.
subbed!!
I am not an Indian but what's wrong with being an Indian? Stupidass
He means adorable and brilliant guys are indian
curios boi bad english skills and hard to understand
that's not what he is saying he's saying that most programmers are indian, and he is not.
Ha ha ... too many Indians in your 'brilliant and adorable' list? It's ok, we like this guy too!
When you called fib(n-1), did you leave out the second argument memo on purpose?
That was not the original code... check the original code in the description. There, he made two different functions fib() and memo()
Great video!
Easy to understand and made concepts crystal clear.
Thank you!
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 UA-cam 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.
Make some programming video on your pc
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
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!
This video is everything. You've got awesome teaching skills. Thanks so much for taking the time to share your knowledge.
What is bottom up approach in programming?
Hey YK! What is the best book/textbook to learn programing and basic CS?
JJfrancay there's plenty of books you can find on Amazon but I highly recommend something like Codeacademy. Very good resource for basic cs.
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.
Love the simple breakdown of this.
Thank you. I really couldn't understand the difference between the 3 approaches from textbooks until watching your video.
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
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.
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.
Yup
Actually, wouldn't it need to be a global variable? Passing in memo wouldn't help us "remember" the result, would it?
Never mind, just realized it depends on whether we are passing by value or passing by reference.
@@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.
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!!!!!!!
Awesome stuff. You explain the concepts well. Many kudos.
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
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.
0:40 Fibonacci sequence starts with 0, 1 by the way.
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 ^^
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.
Your videos are amazing man. You explain difficult processes easily and this is exactly what I needed at the moment
The video is great. You explained the concept very quickly that what exactly it means in a simple language without wasting time on other things.
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 ....
@Chris Blackwell still don't get it... :( can you give an example? is number of operations for fib(3,memo) = 2n+1 ?
@@danielchang2487 Did you find out?
@@joshking9537 not yet..
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.
@@danielchang2487 imgur.com/a/7x0yQiw
You don't even need an array in your "bottom up solution"
can you calculate it on the fly without array?
@@YassineAbdulRahman of course, you only need two variables storing two previous values.
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
@@chiragasourabh6044 That's exactly what i thought but its O(n) is bigger
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
dude you are a legend. helped me so much with my dp project. so much more helpful than my prof
Wish your channel was available when I did my undergrads. Great stuff.
didn't understand the part starting from 7:43 when the explanation for the second 'if' starts, explainig why it is n times
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
aaaaah!
"computation"!
not competition!
had me confused there
Thanks for giving insight on Why to use bottoms up approach. Very good.
Your super power is turning abstract concepts into chunks that my brain can consume,.. programming alchemy. Gold!
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)
Mazen Abusharkh isn't it simply better to declare memo as global and never pass it...?
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
Mazen Abusharkh checked the comments only to see if anyone else recognized it :D
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.
Not making everything global is a good habit. But in this case its ok
Big O notation please!!
David Vasquez google it
Thank you so much! Memoization/recursion/bottom up were getting hard to differentiate/ see how they work together. This helped alot!