What can âThe Simpsonsâ teach us about Dynamic Programming?
VloĆŸit
- Äas pĆidĂĄn 28. 10. 2021
- An introduction to dynamic programming, how to approach these types problems, and we'll step through a few basic ones.
đ Recommended books (on Amazon): www.amazon.com/hz/wishlist/ls...
â€ïž Support me on Patreon: / simondevyt
đ My Gamedev Courses: simondev.teachable.com/
Disclaimer: Commission is earned from qualifying purchases on Amazon links.
Follow me on:
Twitter: / iced_coffee_dev
Instagram: / beer_and_code
Github: github.com/simondevyoutube/
Covering dynamic programming, top down vs bottom up approaches. What is memoization and tabulation. Will also answer a few quick problems like the Fibonacci series, Coin Change, Min Path Sum, 0-1 Knapsack, Subset Sum, and the Staircase problem. - VÄda a technologie
choosing a name "because it sounded impressive" feels very much like a developer thing to do!
We call that Impressiveness Maximization Naming Schemes.
there is nothing worse. i fucking hate people that make future things harder to learn by naming them poorly
@@leeroyjenkins0 What you're referring to as Linu- ah, carry on
â@Jorge C. M. I use Arch btw.
@@mrpedrobraga *Perceived Impressiveness Optimization and Maximization Nomenclature Enhancement Proposal
You just broke down this problem of understanding Dynamic Programming into subproblems that were so much easier to understand! I literally just had my teacher take 4 hours of class in total to explain this and you did it in under 15 minutes. You of course have earned a new subscriber.
Well then you in total spend at least 4 h and 15 minutes on understanding this problem.
@@larryd9577 That's awfully charitable towards traditional education :(
@@larryd9577 Yeah I love how people ignore priming the idea and then when they revisit it they think they were taught correctly.
The fact that dynamic programming was named because it sounded impressive makes me feel better that my open source project got it's name because it sounded like something an open source project would be named.
which project did you create?
Yeah, your approach is way better because it communicates something relevant.
Just randomly appending -ng to my open source projects to sound legit
The word "dynamic" usually implies that time is an element of the problem (as opposed to static). However, as far as I can tell, the only role time plays here is that it takes time to run the programs. I'm glad you are here to explain this to us.
You are like fireship but MORE nerdy â€ïž
I've never heard that dynamic programming solutions include memoisation until now. Recursive algorithms that seemed slow and restricted to me now make so much more sense!
Dynamic programming can come as a lot of those intimidating subjects, BUT not if the teacher is Simon!
Iâm really impressed with your content. I wonder why you donât have a million subscribers yet. Thanks for taking the time and explain these tricky concepts in such an approachable way!
I've written DP algorithms multiple times for comparing discrete sequences which is the min path sum problem you described. Or finding the minimum cost path through a 2D matrix from the bottom-left to the top-right. There are a few different ways to write it depending on how general you need it to be. It easy to lose sight of the generality of DP but you described it really well. Thanks
I thoroughly enjoy your videos! As a web developer I find it extremely cool that you are talking about complex topics, but ground it in javascript and web browsers. I am looking forward to more game / 3D videos as well!
Simon, thank you so much for being a presence on the internet. As someone in the industry with big dreams, your guidance is of great value to me and I hope one day to pick up new tasks and build things like you can.
My pleasure!
Wow, easily the best tutorial on the intimidating Dynamic Programming topic! Thank you very much!
First time viewer. We were taught DP in uni. This clip should be included in the References section. It is really intuuitive what you say. Thanks for this!
fibonacci is dead simple if you use a loop where i < n-2. In the loop do: next = a+b; a=b; b=next; and then return next after the loop.
1:06 this guy sneaks in the most hilarious easter eggs with inspect element
lmao the wiki page edit
You blew my mind. I was so afraid of DP before but you made it look so simple. Will definitely get back to SP again now
Yeah, at it's core it's just keeping a record of what you've already done so you don't have to do it again. For repetitive problems this can lead to some crazy efficiency gains. I think Fibonacci is so popular as an example because the difference between a memoized and non-memoized recursive Fibonacci algorithm is so stark, it really drives the benefits home. Like, a modern PC will struggle building out Fibonacci trees past 50 for the non-memoized version, but numbers in the millions aren't a problem for the memoized version.
The real struggle for dynamic programing is understanding the pieces so you can adequately memoize the problem. But, that's the real struggle of all programming, so nothing new there.
Your voice is so relaxing, I feel like I can listen to these tutorials for a whole day
You make everything sound less intimidating and fun.
Got yourself a subscriber. I love it. Love the whole explanation and the demos. Thank you SimonDev
All of your videos are pure gold!
I love how you end with " hopefully that was helpful" . Man this another tier of quality teaching. thank you !
Great explanation! This was definitely something I just glazed over in the past because it sounded complicated.
Some of your topics are way above me but I love your style! Always a treat to see new uploads!
excellent simplification of a complex subject
This channel has my favorite computer graphics content on all of youtube !
This video is solid gold. I've found a neat new tool for working through LeetCode exercises after watching this. For me the 'click' came with seeing the problem break down to two distinct parts. The recursion part for making the problem smaller and the combination part for how to glue the results from the smaller problems back together.
Its basically caching/storing frequently accessed function/calculation outputs, for a bigger function or the same function with different parameters using recursion or iterative approaches or even just basicall function calls to another function.
Man, I love they way you explain! Cheers
That subtle family friendly Scarface reference got a good chuckle out of me. Subscribed.
As you have shown, the first step is to find a recursive solution; then you cache the sub-solutions (memoization); then you get rid of the recursion and compute it bottom-up just to flex (dynamic programming.)
In my experience as a TA, CS students that struggle to learn dynamic programming actually just struggle to understand recursion, so they can't even get the first step done.
Recursion is definitely one of those slightly weird ways of thinking, got any tips on how you help those students out?
@@simondev758 I encouraged them to change majors.
@@dkosmari Hah, harsh
In order to understand recursion, unless there is nothing left to understand, you must fist understand recursion a little bit less.
Some things never change -- I started my CS degree over 20 years ago with basic C programming. The pacing was fine, and nobody seemed to struggle. The class thinned out a bit when pointers & recursion were introduced, though.
Part of me wonders whether we just suck at teaching it, or whether there's a group of people whose brains just don't work that way. Or both.
There was a cool online lecture by MIT with that super hot professor that used dynamic programming to figure out optimal fingering patterns for playing a guitar song and it was amazing :D
Not only excellent content, but your voice makes everything better lol
8:30
I used to work at a major tourist destination in southern California. One time when I gave a Canadian kid a US $1 coin as part of his change, he was quite excited to discover that they existed. đ
I didn't know US $1 coins existed either! Learn something new
@@simondev758 I don't know what the current series is, but in the past, the $1 coins have featured Susan B. Anthony, Sacagawea, and US presidents. The kid said something like "I didn't know America had Loonies." If I was more quick-witted, I might've said something like "You might not like [historical figure], but I don't think they were loonie!" đ
@@AlyssaNguyen Hah, have it saved up for the next kid!
Great video! As usual.
I don't see why some people would consider the recursive solutions simpler -- the iterative solution to Fibonacci numbers is literally just how any sane person would solve it with pencil and paper, just automated with a computer, a for loop, and the a couple local variables to cache the last two results.
It is one of the Best programming tutorials ever.
The Easter eggs you put on your videos are really funny to look at, like the fake resume stuff at 1:12 and some other video of yours had a fake game design document too. Yes I'm binging.
this isnât quite a fake resume, itâs a fake Google âpromotion packetâ (a thing that you spend days working on in an effort to convince a committee that the work youâve been doing means you deserve to get recognized with a higher job title and pay. you go over each of your big projects in agonizing detail, justifying it relative to team and company goals and âimpactâ, and solicit coworkers to effectively be your hype men. so itâs a lot like a resume, but in much more detail, often running to about ten pages of fairly dense text. it was an immensely time-consuming and widely loathed process, and had only a limited effect as compared to your managerâs feedback to the promo committee. I am no longer at Google but I understand that the process has changed significantly (even before the time of layoffs), though I do not know what the changes entail nor the effect that it had.
(hello, I was formerly pfish@)
"those aren't nails and broken glass, those are prizes!"
Fantastic video and content in general.
Oh man that was soo good! Thank you :D
Great video! I'm a huge fam of this channel
Well done! Excellent video, I love your voice!
You are awesome Simon. Would love to pick your brain someday.
Of course you earned a new subscriber, that is beyond obvious.
Your videos are inspiring to an Unreal developer who wants to have a tutorials channel!
It looks so natural, and so well planned at the same time.
Thanks a lot! Please, keep it up :D
You look like you're well on your way, already at 14k!
It's mostly from an old modeling video that got traction because the creators of the character shared it. Very misleading haha
1:24 "the RAND corporation... vampires, are forcing our parents to go to bed" xD
We're through the looking glass here, people
1:03 Who also saw that picture of SimonDev in the bottom right corner?
great ( as usual !)
Well for file based "memory", one could just hash the problem, pop the state of the solution in a file in a directory with that hash, and then if another problem generates the same hash you can just check all the files in that directory to see if it the solution was already started before, sure a few extra details will be needed to identify if the solution is for the same/similar problem but that's relatively easy to add
def f(n):
if n==0:
return 0
a,b=0,1
for i in range(n.bit_length()-1)[::-1]:
a,b=a*a+b*b,b*((ai)&1:
a,b=b,a+b
return b
fast fibbonaci function in python.
It's asymtotics O(multiplication) ie the speed of calculating a fibonacci number is around the final multiplications speed.
Heh neat, I've never seen that.
@@simondev758 Video on fibonacci.
czcams.com/video/Ct7oltmdJrM/video.html
f(2n)=f(n)**2+f(n-1)**2
f(2n+1)=f(n+1)*(2*f(n)+f(n+1))
Using the binary expression of n, can get f(n) by repeatedly adding 1 and doubling.
As an IE, my favorite DP algorithm is the Wagner-Whitin algorithm. :)
My goto example for DP has always been calculating n factorial, but like you mentioned its just a different hat.
best CV ever!
"in a way, dynamic programming is just like a morally dubious transaction of sugar-based power"
Top-notch rĂ©sumĂ©! đ€Ł
Thanks!
Thank you so much!
No, thank you!
Thank you.
Thanks! Very cool.
How/with what tool do you create your sketchy diagrams?
Chrome canvas
Interesting!
Oh that's why we spent a week on fibonacci heaps in uni. There *was* a reason! It just took a youtube video 5 years later to understand.
Brilliant!
You sound like the Coach McGuirk of Computer Science. I mean, without the laziness and stupidity. I mean it as a compliment, of course. You're great. You make data structures fun. [-ish]
Had to look up who that was... and I see it's another H Jon Benjamin character hah
4:11
The clown will always watch us from above.
All his blessings fall from the top.
My man, can you make more videos like this? (on javascript)
In ts/js instead of using plain object as cache, use Map instead. It's much faster when it comes to adding new things
Good video on dynamic programming, but mentioning the Simpsons here seems kind of forced to get some extra attention (and its just for top down/bottom up while dynamic programming is also about memoization).
I mention memoization in the video.
As for names, yeah, naming is hard. I'm still learning the in's and out's of making a good one. I've been getting some help with them, and this was a part of a change of 4-5 titles. This was a bit of a "try it and see" type of name. It's doing substantially better than the previous, boring title, but could still be much better.
You kinda have to try them out, see how they do for a week or 2, whether or not they improve views, and then try to brainstorm another. It's pretty crazy, but just subtle naming changes can bring you from obscure to large numbers of views. You'd think that just making the video was enough, but that's only the beginning.
I thought "dynamic programming" would be generating (and compiling, if it's a compiled language) executable code at run time.
That exists too, it's called JIT! (Just In Time) compilation
I did that once. I made a function that generates a GLSL shader based on a set of features, for a game "engine" that I've been working on.
1:06 - SimonDev, thought to have discovered common sense. He described it as the ability to just use your goddamn common sense.
Have you made a video applying backtracking to these problems?
Don't have one planned right now, really surprised this video suddenly got attention. I think I made it in 2021?
one reason modern games are such big downloads, right? 50GB of "assets" does not mean artists crank out crazy big files, they prebake most stuff so you dont have to wait 5min on your first startup of the game
This may be a noob question but is there a reason why you stringfy the key? Why '' + total instead of just total?
Great video btw
If the function takes an array or other object, then it wont work because of how comparison works with object. If two references to the same object are compared, they will be the same, but if 2 objects with identical data are compared, they will be different. For example `{} == {}` is false, but `a = {}; a==a` is true.
I'm web programmer: angular, node, vue, etc... I love your vids but understand very little... đ Any advice?
pause at any point you dont understand something and look up more information about it, that's what i've been doing with his latest few videos since they go a bit too fast for me
Aw man I didn't realize I was moving too fast :( I like to try to pack as much info in as I can heh
As for advice, pretty much just like Ramones mentions. Pause, write down, rewind, repeat until things sink in. Nothing comes easy, at least to me.
Feynman method. Learn some of it. Write your own lecture notes as if you were going to teach a class on it. Whenever you get stuck or can't explain something, go study that part more. Repeat.
@@simondev758 It's normal paced for you, but for us mortals đ„ș, lucky we can pause and rewind
I found a ton of good classes on the channel education 4u , the cg playlist starts with cathode ray tubes and ends at 3d transforms. Also, the cmu database groups youtube is a goldmine for data structures and algorithms . I think learning cg is hard to pin down for external reasons too. Opengl is like a mix of both a program api AND a hardware api . As in, gpu/cpu vendors have to ship their products with an api the os can talk to. that means not everyone wants to support that, hence apple drops support for opengl and we get vulkan from amd. Also, gpu manufacturers want to put in tensor cores for ml but maybe not relevant for cg so they shoehorn some apis. Tldr , i find history of cg important to understand the APIs
i think there is a tangent worth adding
most of the time you have to decide to optimize for cpu or memory, this is very much deciding to optimize for cpu and increase memory usage.
That might very well be worth the trade, but at times its not
Look what they (imperative style) need to mimic a fraction of out (declarative style) power.
thank you Bob from Bob's burgers
At 7:12, you mention that not all of the dynamic programming problems are similar in nature. Do you know any common DP problems that do not fit the common form you talk about?
Picard and Dathon at El-Adrel
Hey boss about that paycheck i still havent got it
I work for a FAANG company, I've interviewed candidates⊠I don't think the questions we've asked fit those patterns thoughâŠ
I've never used a dynamic programming style question, although I have seen a couple colleagues use them. My experience is limited though, I've only been an interviewer at Google, where they had an internal questions site you could grab questions from. And when I was interviewing, that was 12 years ago, I'm sure things have changed quite a lot since then.
@@simondev758 We have team-wide list of questions here.
This was a long way to describe life, and the problem of automation.
This was an amazing video, but..... What does it have to do with The Simpsons?? Like when did you even mention it in the video?
loved the simpsons references
I knew this under another name: Divide & Conquer pattern.
Yeah they're superrrr similar. When you have optimal solutions without overlapping sub-problems, you have divide and conquer.
you sound like bert from big bang theory
Liking more of these educational programming videos rather than the gaming ones. (Though I do miss the gaming ones lol, I actually made a simple game of my own from everything I learned in your videos )
More gaming ones eventually, people have asked for a few more in this series so I went with it a bit :)
@@simondev758 nice. Itâll motivate me to keep going. If youâd like to see what Iâve created due let me know :)
I feel like I could more easily convert iron to gold compared to becoming as good as him in coding.
Savage
god I hope you dont have 50 of these comments already but $1 and $2 coins are super common in the US too. We just don't get fun names :(
Seriously? I lived in the US for a while and never saw one, so I thought they didn't exist, but I didn't bother to look it up heh
Like:dislike ratio on this video is crazy. Unless my browser extension is lying, it's 3K:20, so more than 99% liked.
Yeah I'm pretty happy with that, I spend a lot of time planning them and it's good to see people enjoy the work
there is a better way to find a fibenacy number and a better sollution for coin change, just saying
subset sum problem can be solved with a queue for O(n) time complexity
You sound a lot like Garbaj
A really horrible name for something that didn't need a name
Breaking a problem into small problems and cache the results of the smalls problems is basically common sense and life.
I am going to come up with a new term "Multi-Schematic Programming": it's the process of writing a code as lines of text, group those lines in groups named "files" and group those recursively in a top-down tree structure where it's intermediate and root nodes are named "folders".
Give me my "Multi-Schematic Programming" wikipedia page.
I love it. You're going to make a lot of money selling courses on multi-schematic programming techniques.
Just use a functional programming language and make your life easier. :D Or at least, in javascript, a functional library like ramda, crocks, sanctuary, etc.
I actually haven't done much functional programming beyond whatever was covered in university. I should go back and try a bit.
@@simondev758 I feel like a lot of what you are discussing here is covered almost by default in functional programming. I'm no expert though. Keep up the awesome videos!
@@sarajin Possibly, I don't know enough about those languages to say one way or the other.
Kinda guessing though that if anything, they just may make certain patterns more or less accessible? This is pretty just general problem solving, FAANG type of interview questions, wanted to show that there's actually not a lot here that's scary.
I really want to spend some time in some functional languages though, got any recommendations on where to start?
yeah I was extremely confused by this video because this is the absolute bread and butter of functional programming. it doesn't even have a name; it's just what programming is. MUCH more importantly, functional programming allows us to recognise the huge structural similarity of all the code solutions that were presented, and lets us write that similarity AS CODE. all those solutions could be represented much more concisely and modularly.
Making this video was really just a sub-problem for the larger problem of growing your channel. Now if only we could cache the solution. đ€
Love it
easter eggs
Maggie Simpson did
Haha that wikipedia page
The video glitched somehow. I don't see the dots above your "i"s.
why call it "dynamic" if it's something you pretty much chisel down in stone? If AI/AGI would understand it's own code completely and continually rewrite itself from "scratch" and rewrite it's own compiler to run as efficiently as possible on the hardware it's on, I'd call that "dynamic". This seems like the exact opposite, aka "static"
I didn't name it