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
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! 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.
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!
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.
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
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!
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 TH-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 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!!!
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
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 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
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!
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 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 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!
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.
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!
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
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.
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!
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!!!!!!!
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
@@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
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.
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!
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?
I have a masters in computer science, and this is the first time I've seen this concept explained this well. Had you been my prof way back, I'd definitely have gotten better funding in grad school!
This is the best explanation of DP on TH-cam. Have exam in 2 days and this really helped me in understanding basics. Thanks for this. Keep making more such videos.
Can you please cover the pattrens discussed in this course www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews?affiliate_id=5457430901161984
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 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
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 🙂
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.
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😃
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.
Hi, Great video. For bottom-up solution your space complexity is O(n) since you create an n-array. You don't need to store all the values. You just need n-1 and n-2, you could store them in 3 item array and update the values with each iteration. So time-complexity would be O(n) and space complexity would be O(1) Here's the code; public double fib(int n) { if (n
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!
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.
Took me a while to fully grasp the entire video but regardless I got it all now. Use this as a friendly reminder that smartness is not what matters but what does is the decisions you make to keep trying because you will get it done.
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
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
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 TH-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.
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)
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
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.
In the bottom up approach you can get the Space complexity down to only O(3) as you don't need to store the whole array, just the last 2 values calculated, and only where n>=3, when n
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.
@@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.
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!
Make videos for more complex programming questions (generally asked in interviews and technical online tests) which can be done by dynamic programming.
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.
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!
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
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 ....
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
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
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.
A way I think of this now is the memoized == top down approach, where the main problem is solved by solving sub problems that it only needs for the specific problem(s). Where as the bottom up will solve every sub problem immediately. So clearly 1 approach is better than the other for different needs. Thanks for the video, helped me understand.
Quite funny. Been giving first year physics students an algorithms course for a while, and basically everyone starts out writing the sequence in a "bottoms-up" approach. When they find out they can use recursion, they're like: "That so cool and elegant!" until they realize the sometimes "uglier" approach is much more convenient. Thanks for the video!
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
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!
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
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
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 TH-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 keep coming back here for a refresher every time I have an interview scheduled. Love this
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!!!
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
Smart, Humble and Simple. You're the best my man.
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!
The fact that the most efficient solution is so freaking simple is amazing.
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
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!
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 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!
The way he has explained is simply amazing....
Your super power is turning abstract concepts into chunks that my brain can consume,.. programming alchemy. Gold!
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
For free... dude, u are goat. People these days dont know how much technology, with a good use and being aware of his cons, can help.
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 know how to teach people. It is really helpful.
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.
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!
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
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.
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: th-cam.com/video/oBt53YbR9Kk/w-d-xo.html
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!!!!!!!
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
Man, the best explanation in TH-cam, I've been trying to better understand a topic for about an hour.
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.
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.
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!
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!
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 😭
I have a masters in computer science, and this is the first time I've seen this concept explained this well. Had you been my prof way back, I'd definitely have gotten better funding in grad school!
This is mind-blowing! Thanks, Dojo.
This is the best explanation of DP on TH-cam. Have exam in 2 days and this really helped me in understanding basics. Thanks for this. Keep making more such videos.
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
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!
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
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
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 🙂
the best explanation i have seen on DP till now which covers all aspects of DP - naive, memoized and bottomup, excellent work!!!!!!!!!!!!!!thanks
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.
This is THE best DP video on TH-cam! The example you use is very simple but you really helped me understand what this approach is all about
It's so simple. Thanks 😊
Please make more videos on dynamic programming.
😓😓😓simple....
the best explanation of dynamic programming I've ever seen
lots of love from India brother, you are awesome in explaining things in detail. god, bless you.
My Bachelors would have been a lot more awesome if I had a teacher like this guy!! Great explanation. So glad I found this channel!!
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.
Hi, Great video.
For bottom-up solution your space complexity is O(n) since you create an n-array. You don't need to store all the values. You just need n-1 and n-2, you could store them in 3 item array and update the values with each iteration. So time-complexity would be O(n) and space complexity would be O(1)
Here's the code;
public double fib(int n) {
if (n
amazing explanation, thanks :) keep up the good work man!
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!
THANK YOU SO MUCH : well explained
I learn things faster by watching rather than reading and you are simple awesome.
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.
Took me a while to fully grasp the entire video but regardless I got it all now. Use this as a friendly reminder that smartness is not what matters but what does is the decisions you make to keep trying because you will get it done.
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
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 TH-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.
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
In the bottom up approach you can get the Space complexity down to only O(3) as you don't need to store the whole array, just the last 2 values calculated, and only where n>=3, when n
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.
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!
Make videos for more complex programming questions (generally asked in interviews and technical online tests) which can be done by dynamic programming.
2 hour lecture explained in 14 minutes, thank you
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.
Earlier I thought DP is very hard concept,but after watching this video,I got interest in DP,thanks CSDojo
Amazing video.....I love your videos. They are really helpful 😇.....Keep going, more power to you🎉✨💪🔥
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!
Make some programming video on your pc
Thank you. I really couldn't understand the difference between the 3 approaches from textbooks until watching your video.
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()
oh man...You literally nailed all that stuff in a few! A bigggggg time appreciation from me.
Can all DP algorithms be implemented with a bottom, up approach?
I'm having a hard time trying to learn this topic via an internet course, your tutorial clarifies this important issue , thanks alot
aaaaah!
"computation"!
not competition!
had me confused there
By seeing ur video and ur explaination ,it obvious that you have a deep knowledge of dp.
What is bottom up approach in programming?
You are doing a great service to humanity. Thank you.
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.
dude you are a legend. helped me so much with my dp project. so much more helpful than my prof
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
Clear explanation with an easy example. I really love the coding part and show the time difference!
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
Who the heck disliked this??? This is an excellent explanation!
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
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.
Minor: Actually fibo starts with 0 and 1. Not with two 1s
It starts with: 0, 1, 1,...etc
@@William_Clinton_Muguai Well zero is optional. It adds nothing to the sequence.
The naive fib starts zero,one. The fib method can be used with any 2 seeds with interesting and amusing results
This video was super helpful! The first time I saw dp, it was explained in a very complex way. This is so simple!
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.
U r the best teacher tough topics become easier when YK teaches. Thank u so much. God bless u.
14:07, the largest number I ever seen
This man is an absolute genius
GIVE ME YOUR PINGUIN
Bottom up is absolutely my favorite and most simple and efficient of them.
A way I think of this now is the memoized == top down approach, where the main problem is solved by solving sub problems that it only needs for the specific problem(s). Where as the bottom up will solve every sub problem immediately. So clearly 1 approach is better than the other for different needs. Thanks for the video, helped me understand.
Quite funny. Been giving first year physics students an algorithms course for a while, and basically everyone starts out writing the sequence in a "bottoms-up" approach. When they find out they can use recursion, they're like: "That so cool and elegant!" until they realize the sometimes "uglier" approach is much more convenient. Thanks for the video!
Excellent explanation. This is the best channel I've found for preparing for coding interviews!
Bottom Up approach
temp1 = 1;
temp2 = 2;
for(i=2;i