The worst problem about the Leetcode interview process is that is forcing engineers to memorize instead of thinking. If 20 years ago someone told me that in the future we will be selecting engineers based on a memorization process I would laugh. In a job market where everbody memorizes patterns an algorithms, these kind of breaking a problem in parts explanation is fresh air
i really hate that too. I am a strong advocate for easier problems with more scrutiny on explanation and correctness. There's nothing more I want to see gone that questions that have an easy to remember trick solution and poorly trained interviewers just looking to hear THEIR answer.
@@DecodingIntuition indeed. It probably has a higher recruiting cost but I would rather evaluate the thinking process of a candidate instead of the same candidate faking that thinking process because he grinded that Leetcode exercise
To be fair, it is really hard if you don't know that DP is not about drawing arrows on random tables. Once you get comfortable with the idea that you can efficiently use a recurrence relation to simulate all possibilities, coin change really does become as easy as "take the coin or skip the coin" :) I'd really love for him to see this video and see if it changes his mind about it, because he's a smart guy and I'm sure if he knew what dp actually was he wouldn't have spent over an hour on it trying to pass art class
DP is hard because the algorithms look like a complete enumeration, especially in optimization problems. Half of the process is to convince yourself that the memorization you've thought of saves enough time in your specific case. This approach with cached complexity simultaneously derives the algorithm (just enumerate every state via recursion) and calculates the complexity for you (the recursive call is O(1)). It is then easier to derive a non-recursive algorithm from the recursive, and the memorization table is a matrix with a dimension for every argument of the recursive call.
Cleanest DP intuition video on RUclips, I have watched countless of them but this step by step like exactly how we think during an actual problem solving process is what connected with me. I really wish you make more videos but from the perspective of how a person who is leaning will think and solve it.
Please, I need you to MAKE MORE VIDEOS. I don't care if it's about the most useless data structure or algorithm of mankind, with this video you show that intuition and the process of building a solution is imperative to understand whatever THE solution to the problem means, even if it's a hard problem. I urge you to keep making videos, you help people like me (too much). I REALLY appreciate the time people like you take to explain any concept. Thank you very much.
@@DecodingIntuitionanother person here - I share one for one, exactly what this person has said. There really is NOT a lot of people on RUclips that walk through the ENTIRE problem AND process. Please continue making content bro 💪🙏
@@Hellbending That's my goal! I don't just want to tell you why I know a solution works, I want to show how I arrive at it. There's plenty of great content that explains why things work, but I'm here to try to fill the gap for the other :)
Really just getting started into programming and a friend sent this video to me. I think I got quite a bit of it, but this gives me SO much stuff to go and track down and learn. THANK YOU!
This was genuinely mind opening. Thanks for this. It's not often you feel like you a video has made you better off after having watched it. My perspective on problem solving has improved having watched this. Now its all about practice.
Today I learned that this fancy "Dynamic Programming" I've been hearing about is literally just a scary word for basic step-by-step problem-solving to avoid duplicate computations, and I had no idea developers out there don't know how to do that
Yeah I got to the end of the video and still didn't understand what dynamic programming actually means. I thought the program is somehow "dynamic" (whatever that means because pretty much all useful programs are dynamic in some way), but it didn't occur to me that it refers to what the programmer is doing in order to come up with a solution. To me that's just normal programming. Or have I still missed what exactly it is that makes it dynamic as opposed to not dynamic i.e. static? Does it literally just mean thinking? Surely not.
@@brandyballoonAccording to my lecturer the man who came up with the name called it that because the higher up in charge of funding had a reputation for disliking mathematics so he tried it to make it sound like something different
I started Programming two months ago with high intent to go competitive. This is my favorite vids as of now that makes me comeback for another watch every 2-3 days or so. Absolutely beautifully taught
after an year of being into the DSA space, I've now realised that I had not improved my problem solving capabilities by much. I just learnt the concepts that were being taught, and developed pattern matching abilities, NOT PROBLEM SOLVING ONES. Also, Now's the time I realise that the reason I love math is because I could develop the pattern matching skills within a short period of time, thus acing my tests. Thanks for changing the way I thought about math, cs and problem solving in general. This beginner shall now set on the voyage to become a problem solver, a great one, god willing.
20:28 This meme highlights the main misconception I have had forever, also loved the department of defense trivia. Holy moly the fact that no one ever mentioned or highlighted that recurrence relation != recurrence execution to me before is such a scam. In fact I was made to think recurrence execution is what happened in the call stack (even though I didn't know how physics allowed it). SOOO GLAD to have cleared it up. Drawing down the entire trace graph of calls always got me stuck and felt unintuitive, since I didn't know how my computer processed it. I also got lost when drawing it down. "Decisions are Values to compute once and not task to run every time" THIS QUOTE AND VIDEO IS LIFE CHANGING Its funny I got a non-dev job as a new cs grad, but videos like these are perfect/motivating as I love problem solving and want to keep my skills sharp even if my work right now is in a different field. Since problem solving is a universal skill. Can't wait for the next video since I never truly understood memoization and other space/time optimization that people usually did when solving such DP problems. Or even other LC type problems. I just love that you are focusing on problem solving more than just leetcode, please keep it up!!!! This is a niche (math/cs/leetcode/problem solving) that i always thought lacked good youtube content.
@@GRAYgauss it's only "not actionable" if people make promises they cannot keep. it's a simple rule of thumb: if you aren't sure you can keep your promise (to the best of your ability within your control), don't promise. extenuating circumstances such as death and traffic apply. for our own sanity, we must assume that lexical and logical ambiguities of promise statements have been previously resolved and agreed upon by all involved parties. for example: Scenario 1 - Alice knows they have (2 + n) chocolates in their chocolate tin, such that n > 0. Alice promises Bob 2 chocolates from their tin. Alice then gives Bob 2 chocolates from their tin. Nobody knowingly made impossible to keep promises, everybody's happy. Scenario 2 - Alice knows they have only 1 chocolate in their chocolate tin. Alice promises Bob 2 chocolates from their tin. Alice is clearly lying and should not be trusted with the secrets of Quantum Physics. Oh, and not to keep promises, either. Scenario 3 - Alice knows they have (2 + n) chocolates in their chocolate tin, again such that n > 0. Alice promises Bob 2 chocolates from their tin. When Alice and Bob open the tin, the chocolates are all melted. "It's okay," Bob says. "It was only thermodynamics." Nobody knowingly made impossible to keep promises, everybody's happy. feel free to ask any questions or present your viewpoint. i'm happy to discuss my viewpoint on this subject further.
These videos are very thought-provoking. I really like the presentation of this concept, which has traditionally been hard to follow. One request: I have found that the best way to truly integrate a new concept is to have both a good explanation, and also several fully worked examples. This lets me “triangulate” the concept better. Would you consider uploading a third video where you just work two or three full examples using your approach. No need for a lot of explanation, your first two videos cover that, just provide several examples we can use to triangulate the essential characteristics of this tricky concept?
This video is so good. Not just for DP, but general problem solving. Also, I really appreciate the notes slides you put in the video, that saves a lot of time and helps me understand the content better. Instant sub.
THANK YOU, this video is really opened my mind. I have solved 300 problems on Leetcode, and I can solve most DP problems, but my confidence on DP is little. Your process to observe/break down a problem is phenomenal, and I feel like it just should like this all the time. I will share video to all my friend who can code, and just try to solve the two DP problems that I can't solve.
The part about time complexity and thinking about the size of call stack in terms of unique states is really great, I've never though of computing the complexity that way before even though it seems intuitive when you actually think about it
Please do make these kind of videos more often, I am a software engineer for over a decade now and I feel to go back to roots again just because of this video :)
This video is amazing! The confidence you express your ideas with, combined with you immediately backing them up, really helps the ideas settle in my head. I especially liked the example problems at the end, after watching the video I had no trouble at all, which is usually not the case for videos claiming that something is "easy". I didn't even especially struggle with dynamic programming in school, but this definitely helped cement my foundations. Thank you!
awesome vid, coin change being the example here is a huge bonus for me because that problem has been fucking with my head for a while even after looking up the solution
The DP section of this video is good, but the greater value I garnered from this was ACTUALLY applying the breaking-down-the-problem strategies we are taught when approaching leetcode-style problems. These are things I have been told countless times but have struggled to break things down to their core components, but after watching you do it in this video it has really revitalized my confidence. Well earned like and sub, keep up the great work! Would love more videos like this.
Your analogy of treating every function call as a "state" with some fixed value and some state variables really helped clarify dynamic programming for me. I bet there's going to be O(views_on_this_video) increment in dp solves on leetcode now😅
20:17 re: Richard Bellman “I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. “An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very inter- esting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Cor- poration was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Cor- poration. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various rea- sons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying-I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the clas- sical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some com- bination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activi- ties” www.researchgate.net/publication/220243993_Richard_Bellman_on_the_Birth_of_Dynamic_Programming
I'd love it if you could share resources to learn such cool stuff or any materials you've used for this video. This is super helpful and thank you for this !!!
simplify problems with a recurrence relation and recognize that naive recursion is not our only option recursive top down memoization iterative botton up tabulation are the two implementations... nice
Really great video! I haven't seen an explanation so in depth and clear. One suggestion I have is to keep the energetic inflection in your voice as you're going over the problem. The voice over parts are great, but then it cuts back to the problem breakdown and you have a more monotone voice. It would make it more engaging and consistent if you kept the same enthusiastic inflection throughout the video 🙂
It will be better for us if u solve this problem in first go , does'nt matter how much time u take but that first time thought process of yours give us more value .
Nice video man. If anyone wants to practice induction, I suggest working through a book that uses theorem provers, because inductive types and proofs involving them are all over the place in those books. So using languages like Coq, Idris, Agda, Lean etc.
@@DecodingIntuition Really liked your explanations man, made me bridge all of the mathy stuff I've been studying to something more "practical" (as practical as you can be with leetcode). Looking forward to the next video!
@theprimetime should check this out. This is an excellent breakdown of dynamic programming. Hope you put more videos up, thank you for putting this together.
What a great video. Content was excellent, and easy to understand. Audio quality was top tier (thank you for that). Code was easy to follow, except Im only guessing that python does automagic memoization? I'm not a python guy. Hope you do many more!
Yep, @cache decorator does that to any function. I liked using that because 1. Recurrence relation is the core idea, manual memoization takes away from the elegance and simplicity and takes up time and kinda distracts from the main point 2. Manual Memoization isn't hard at all. It's just kind of annoying and there's also plenty of examples out there for that 3. When I don't have @cache (which is most of the time since I mainly use C++), I almost always implement it iteratively anyways. Iterative is actually very easy, given you can get the recurrence relation and I'll cover that in the next one
Banger out of nowhere. Thanks for the guidance, though in general you're approach comes with deliberate practice. (Easier for some than others off the bat)
Very good video. I got a google thing in my gmail and I am not as acquainted with leetcode style problems as I should be. I will do the notetaking methods next time I get the chance to do coding problems. Having all the info right there and breaking it down live seems like a good thing to do. Thank you!
I learned coding after learning allot of math and also the idea of induction. From a thinking pattern i found it extremely similar, so idk if this holds for anyone else but personally i think if you wanna improve you DP skills you should also just try some induction problems on paper.
Great video thank you! My only question is, is the cache decorator even allowed in interviews? I feel like that's something they'd get all fussy about.
depends on the interviewer, but yeah you should know how to memoize it yourself just in case. I didn't show it in this video because 1. it's not that complicated and there are a ton of existing tutorials on it 2. I wanted to spend more time on building the recurrence relations and doing the time complexity analysis, which are the actual difficult parts of dp that don't get as much attention
The answer fits into a 32-bit integer
“I don’t care, I’m using Python” 😂
Python so real for that
Faaaacts
I think I clicked on the wrong type of DP
dr pepper
daft punk?
Deadpool?
Dark Purple
dik pusy? :3
Anyone can teach how to solve a problem but no one actually shows how to break a problem into solvable parts like you.
Keep uploading man.
Bro is out here teaching us how to think
Give someone a solution, you help them for that problem.
Teach someone problem solving, you empower them for life.
- ChatGPT
@@DecodingIntuitionit's same as give a man a fish he will eat for a day but teach him fishing he will eat for his entire life 😅
@@amvsekaiyeah but this one didn't come out of chatGPT so i'm not gonna believe it
Bro drops a banger and forgot to give us blanket 🥶🥶@@DecodingIntuition
@@DecodingIntuition Goat status
>randomly appears
>makes by far the best video about a programming concept i've seen yet
keep going man
> accepts and elaborates
> leaves
big chad energy
Then you haven’t seen enough
"big function has been lying to you"
I am now a firm believer in the conspiracy theory that it's all a plot from big function
The worst problem about the Leetcode interview process is that is forcing engineers to memorize instead of thinking. If 20 years ago someone told me that in the future we will be selecting engineers based on a memorization process I would laugh.
In a job market where everbody memorizes patterns an algorithms, these kind of breaking a problem in parts explanation is fresh air
i really hate that too. I am a strong advocate for easier problems with more scrutiny on explanation and correctness.
There's nothing more I want to see gone that questions that have an easy to remember trick solution and poorly trained interviewers just looking to hear THEIR answer.
@@DecodingIntuition indeed. It probably has a higher recruiting cost but I would rather evaluate the thinking process of a candidate instead of the same candidate faking that thinking process because he grinded that Leetcode exercise
It seems the mainstream just has to ruin everything. From tech, to Religion...everything.
Nah the industry aware of this and has actually made interviews 10X harder as a result of it
Primeagen : “CoIn cHaNGe iS hArD”
DecodingIntuition: “…hold my beer…”
To be fair, it is really hard if you don't know that DP is not about drawing arrows on random tables. Once you get comfortable with the idea that you can efficiently use a recurrence relation to simulate all possibilities, coin change really does become as easy as "take the coin or skip the coin" :)
I'd really love for him to see this video and see if it changes his mind about it, because he's a smart guy and I'm sure if he knew what dp actually was he wouldn't have spent over an hour on it trying to pass art class
tbh I found coin change II a lot easier than coin change
DP is controversial but I think it can be pleasurable for all parties involved
???
@@_JoeVer you sweet little child 😂😂😂
@@_JoeVer google double penetration.
@@_JoeVer search up male dp
"reject the callstack"
"return to math"
DP is hard because the algorithms look like a complete enumeration, especially in optimization problems. Half of the process is to convince yourself that the memorization you've thought of saves enough time in your specific case. This approach with cached complexity simultaneously derives the algorithm (just enumerate every state via recursion) and calculates the complexity for you (the recursive call is O(1)). It is then easier to derive a non-recursive algorithm from the recursive, and the memorization table is a matrix with a dimension for every argument of the recursive call.
Exactly! I'll show in the next video how that conversion to iterative is ridiculously simple.
@@DecodingIntuition Looking forward to that next video!
Cleanest DP intuition video on RUclips, I have watched countless of them but this step by step like exactly how we think during an actual problem solving process is what connected with me. I really wish you make more videos but from the perspective of how a person who is leaning will think and solve it.
This is going to go viral, the best educational DP video I've seen
This way of thinking actually changed how I view/approach these types of problems. Thank you!
Please, I need you to MAKE MORE VIDEOS. I don't care if it's about the most useless data structure or algorithm of mankind, with this video you show that intuition and the process of building a solution is imperative to understand whatever THE solution to the problem means, even if it's a hard problem. I urge you to keep making videos, you help people like me (too much). I REALLY appreciate the time people like you take to explain any concept. Thank you very much.
I'll try :) Thanks for the support!
@@DecodingIntuitionanother person here - I share one for one, exactly what this person has said.
There really is NOT a lot of people on RUclips that walk through the ENTIRE problem AND process. Please continue making content bro 💪🙏
@@Hellbending That's my goal! I don't just want to tell you why I know a solution works, I want to show how I arrive at it. There's plenty of great content that explains why things work, but I'm here to try to fill the gap for the other :)
Agreed. Also subscribed 🔥
"a name so long you might think it's proprietary" is legitimately the funniest joke I've heard this week.
Really just getting started into programming and a friend sent this video to me. I think I got quite a bit of it, but this gives me SO much stuff to go and track down and learn. THANK YOU!
This was genuinely mind opening. Thanks for this. It's not often you feel like you a video has made you better off after having watched it. My perspective on problem solving has improved having watched this. Now its all about practice.
Today I learned that this fancy "Dynamic Programming" I've been hearing about is literally just a scary word for basic step-by-step problem-solving to avoid duplicate computations, and I had no idea developers out there don't know how to do that
Yeah I got to the end of the video and still didn't understand what dynamic programming actually means. I thought the program is somehow "dynamic" (whatever that means because pretty much all useful programs are dynamic in some way), but it didn't occur to me that it refers to what the programmer is doing in order to come up with a solution. To me that's just normal programming. Or have I still missed what exactly it is that makes it dynamic as opposed to not dynamic i.e. static? Does it literally just mean thinking? Surely not.
@@brandyballoonAccording to my lecturer the man who came up with the name called it that because the higher up in charge of funding had a reputation for disliking mathematics so he tried it to make it sound like something different
I started Programming two months ago with high intent to go competitive. This is my favorite vids as of now that makes me comeback for another watch every 2-3 days or so. Absolutely beautifully taught
this is a concept i've struggled for so long with THANK YOU
Some of the best vids on youtube are engaging, entertaining, and educational, and you nailed all three. Genuinely great vid
after an year of being into the DSA space, I've now realised that I had not improved my problem solving capabilities by much. I just learnt the concepts that were being taught, and developed pattern matching abilities, NOT PROBLEM SOLVING ONES.
Also, Now's the time I realise that the reason I love math is because I could develop the pattern matching skills within a short period of time, thus acing my tests.
Thanks for changing the way I thought about math, cs and problem solving in general. This beginner shall now set on the voyage to become a problem solver, a great one, god willing.
I mean, math having formulas and all, is very easy to abuse with the pattern matching llm like approach.
What’s DSA may I ask
We need more of these breakdowns like this!!
20:28 This meme highlights the main misconception I have had forever, also loved the department of defense trivia. Holy moly the fact that no one ever mentioned or highlighted that recurrence relation != recurrence execution to me before is such a scam. In fact I was made to think recurrence execution is what happened in the call stack (even though I didn't know how physics allowed it). SOOO GLAD to have cleared it up. Drawing down the entire trace graph of calls always got me stuck and felt unintuitive, since I didn't know how my computer processed it. I also got lost when drawing it down.
"Decisions are Values to compute once and not task to run every time" THIS QUOTE AND VIDEO IS LIFE CHANGING
Its funny I got a non-dev job as a new cs grad, but videos like these are perfect/motivating as I love problem solving and want to keep my skills sharp even if my work right now is in a different field. Since problem solving is a universal skill. Can't wait for the next video since I never truly understood memoization and other space/time optimization that people usually did when solving such DP problems. Or even other LC type problems. I just love that you are focusing on problem solving more than just leetcode, please keep it up!!!! This is a niche (math/cs/leetcode/problem solving) that i always thought lacked good youtube content.
"If everyone keeps their promise, everyone will end up happy." bro just solved world peace in a programming video
You call making everyone keep their promises a solution? If it's not actionable, how can it be a solution?
@@GRAYgauss it's only "not actionable" if people make promises they cannot keep. it's a simple rule of thumb: if you aren't sure you can keep your promise (to the best of your ability within your control), don't promise. extenuating circumstances such as death and traffic apply.
for our own sanity, we must assume that lexical and logical ambiguities of promise statements have been previously resolved and agreed upon by all involved parties.
for example:
Scenario 1 - Alice knows they have (2 + n) chocolates in their chocolate tin, such that n > 0. Alice promises Bob 2 chocolates from their tin. Alice then gives Bob 2 chocolates from their tin. Nobody knowingly made impossible to keep promises, everybody's happy.
Scenario 2 - Alice knows they have only 1 chocolate in their chocolate tin. Alice promises Bob 2 chocolates from their tin. Alice is clearly lying and should not be trusted with the secrets of Quantum Physics. Oh, and not to keep promises, either.
Scenario 3 - Alice knows they have (2 + n) chocolates in their chocolate tin, again such that n > 0. Alice promises Bob 2 chocolates from their tin. When Alice and Bob open the tin, the chocolates are all melted. "It's okay," Bob says. "It was only thermodynamics." Nobody knowingly made impossible to keep promises, everybody's happy.
feel free to ask any questions or present your viewpoint. i'm happy to discuss my viewpoint on this subject further.
"I promise i wont be happy"
Checkmate
@@jansustar4565 "Checkmate," he says, throwing his own king off the edge of the board.
I will NOT keep my promises because I'm lazy and silly and will eventually end up breaking some of them
These videos are very thought-provoking. I really like the presentation of this concept, which has traditionally been hard to follow. One request: I have found that the best way to truly integrate a new concept is to have both a good explanation, and also several fully worked examples. This lets me “triangulate” the concept better. Would you consider uploading a third video where you just work two or three full examples using your approach. No need for a lot of explanation, your first two videos cover that, just provide several examples we can use to triangulate the essential characteristics of this tricky concept?
Thanks for the suggestion. I probably will at some point.
This video is so good. Not just for DP, but general problem solving. Also, I really appreciate the notes slides you put in the video, that saves a lot of time and helps me understand the content better. Instant sub.
This is the video I needed after suffering with DSA, thank you for breaking technique this down!!
You wtf, you actually made it make sense! The missing insight for me was the term and bounds; the way you put it in a table was the missing piece.
THANK YOU, this video is really opened my mind. I have solved 300 problems on Leetcode, and I can solve most DP problems, but my confidence on DP is little. Your process to observe/break down a problem is phenomenal, and I feel like it just should like this all the time. I will share video to all my friend who can code, and just try to solve the two DP problems that I can't solve.
Best breakdown I’ve ever seen. Will probably watch a few more times to fully understand. Hoping you’ll upload more Leetcode videos
The part about time complexity and thinking about the size of call stack in terms of unique states is really great, I've never though of computing the complexity that way before even though it seems intuitive when you actually think about it
Please do make these kind of videos more often, I am a software engineer for over a decade now and I feel to go back to roots again just because of this video :)
This video is amazing! The confidence you express your ideas with, combined with you immediately backing them up, really helps the ideas settle in my head. I especially liked the example problems at the end, after watching the video I had no trouble at all, which is usually not the case for videos claiming that something is "easy". I didn't even especially struggle with dynamic programming in school, but this definitely helped cement my foundations. Thank you!
The density of knowledge per meme in this video is A+
awesome vid, coin change being the example here is a huge bonus for me because that problem has been fucking with my head for a while even after looking up the solution
The DP section of this video is good, but the greater value I garnered from this was ACTUALLY applying the breaking-down-the-problem strategies we are taught when approaching leetcode-style problems. These are things I have been told countless times but have struggled to break things down to their core components, but after watching you do it in this video it has really revitalized my confidence. Well earned like and sub, keep up the great work! Would love more videos like this.
Best explanation on the entire planet, the world needs you, man
Your analogy of treating every function call as a "state" with some fixed value and some state variables really helped clarify dynamic programming for me.
I bet there's going to be O(views_on_this_video) increment in dp solves on leetcode now😅
I am O(so_happy_it_made_sense) for you
Loved the video for so long I have been confused about DP man keep the good work, sending this video to all of my friends right now.
Best leetcode explanation I've ever seen in my life. Please keep making more videos.
always had trouble grasping my head around DP problem but this refresh perspective cleared up so much stuff. thanks for the content!
You got me so hard with that prime hook. Almost closed the tab on instinct, thinking I had made a mistake. Love math, love memes, love this video.
bro i don't know how to thank you. you changed the entire perspective i held. sorry for following u so late
this is seriously awesome, keep up good work, you're gonna go big on youtube if you keep this up, thank you so much
I can’t believe this is your first video! Amazing explanation and entertaining. I would take a course taught by you!
It's your first video? Man, it's awesome. I already subscribed midway the video. Gimme some MOAR!!
This was excellent, thank you 👍. Trying to identify a recurrence relation is a very implementable strategy for solving problems
Man, this video was actually so good and well explained you earned a sub keep uploading more about DSA and Competitive Coding
Future big tech youtuber right there.
I seriously look at coding problems differently now
Same
Omg it's so good to have videos like this. Thanks, man!
Clicked for the DP, stayed for the DP
This actually helped me 10x my leetcode solving. It was basically me doing the rubber duck technique, but it worked
I didn't quite understand the video but base on the comments saying how good this information is, I subbed!
At it's basic essence, dynamic programming is looking for ways to reuse computational steps for multiple steps/iterations of a problem.
Whoa! This was amongst the best videos on DP that I've watched.
Holy what a great video, instantly subbed
Funny as fuck. Insightful as hell. If my maths teacher was as enthusiastic as you I'd likely have learned what inductive thinking actually was.
definitely want more of this. thank you
20:17
re: Richard Bellman
“I spent the Fall quarter (of 1950) at RAND. My first task
was to find a name for multistage decision processes.
“An interesting question is, ‘Where did the name,
dynamic programming, come from?’ The 1950s were not
good years for mathematical research. We had a very inter-
esting gentleman in Washington named Wilson. He was
Secretary of Defense, and he actually had a pathological
fear and hatred of the word, research. I’m not using the
term lightly; I’m using it precisely. His face would suffuse,
he would turn red, and he would get violent if people used
the term, research, in his presence. You can imagine how he
felt, then, about the term, mathematical. The RAND Cor-
poration was employed by the Air Force, and the Air Force
had Wilson as its boss, essentially. Hence, I felt I had to do
something to shield Wilson and the Air Force from the fact
that I was really doing mathematics inside the RAND Cor-
poration. What title, what name, could I choose? In the first
place I was interested in planning, in decision making, in
thinking. But planning, is not a good word for various rea-
sons. I decided therefore to use the word, ‘programming.’
I wanted to get across the idea that this was dynamic, this
was multistage, this was time-varying-I thought, let’s kill
two birds with one stone. Let’s take a word that has an
absolutely precise meaning, namely dynamic, in the clas-
sical physical sense. It also has a very interesting property
as an adjective, and that is it’s impossible to use the word,
dynamic, in a pejorative sense. Try thinking of some com-
bination that will possibly give it a pejorative meaning.
It’s impossible. Thus, I thought dynamic programming was
a good name. It was something not even a Congressman
could object to. So I used it as an umbrella for my activi-
ties”
www.researchgate.net/publication/220243993_Richard_Bellman_on_the_Birth_of_Dynamic_Programming
This is how I coded Fibonacci in 10th grade. Nobody believed me at first when I said I implemented it recursively in O(n).
Dude, that was some quality content.
I'd love it if you could share resources to learn such cool stuff or any materials you've used for this video. This is super helpful and thank you for this !!!
So well done! One of the best videos on DP
This is great. Never been this excited for a next upload
Great video! Looking forward for more. Moving away from tables is a really helpful approach
This makes me so happy :)
This is the greatest explanation of DP I have ever seen
FIRE!!!!!!
THIS IS WHAT REAL PROGRAMMING IS¡
Great vid thanks! Kinda funny that something triggered you enough to make this amazing content, I hope more things trigger you in the future :)
dw I have really thin skin and get triggered easily, so more to come :)
Exceptional video, this makes code problem look fun for me
simplify problems with a recurrence relation
and recognize that naive recursion
is not our only option
recursive top down memoization
iterative botton up tabulation
are the two implementations...
nice
Nice video. Can feel you having fun and I had fun watching too haha
Great video, thanks for your time and effort!!! Pure Gold tbh
Really great video! I haven't seen an explanation so in depth and clear.
One suggestion I have is to keep the energetic inflection in your voice as you're going over the problem. The voice over parts are great, but then it cuts back to the problem breakdown and you have a more monotone voice. It would make it more engaging and consistent if you kept the same enthusiastic inflection throughout the video 🙂
I love how the energy changes from when he's problem solving and doing the voice over.
The side effects tidbit was probably the most important part for me. The subproblems must be pure.
what the hell! just 34 subs?? underrated. subscribed.🖖
Bro just randomly appeared uploaded the best DP explanation video ever.
Looking forward to more videos. Loved your explanations! Thank you so much!
It will be better for us if u solve this problem in first go , does'nt matter how much time u take but that first time thought process of yours give us more value .
Nice video man.
If anyone wants to practice induction, I suggest working through a book that uses theorem provers, because inductive types and proofs involving them are all over the place in those books. So using languages like Coq, Idris, Agda, Lean etc.
I'll actually check that out thanks for the recommendation!
@@DecodingIntuition Really liked your explanations man, made me bridge all of the mathy stuff I've been studying to something more "practical" (as practical as you can be with leetcode).
Looking forward to the next video!
funnily enough I told my new manager about the video I was making and he showed me a doc he wrote where they used dp to make our system more efficient
@@DecodingIntuition coding a dp solution for work must be such highlight lol
all those leetcode hours paying off
I know this subject through and through, and still watched it through just cause it’s so damn good
This has to be the best video on DP. Hope you make more videos on other topics.
@theprimetime should check this out.
This is an excellent breakdown of dynamic programming. Hope you put more videos up, thank you for putting this together.
HAAAANK!
HANK! DON'T ABBREVIATE DYNAMIC PROGRAMMING.
HAAAANK!
If you abbreviate it, it might be too hard.
Great video! By any chance you go through how you think about solving a DP problem iteratively bottom-up instead of top-down recursively?
Great video, this is the youtube recommendations I want to get!!!
man please make more leetcode solution videos or stream you explain very well
Great shit can’t wait for the next video
2:27 ”different view of not only DP, but also problem solving - as a hole” - I get it now, DP and holes go toghether, makes sense
Great video, can't wait for more!
What a great video. Content was excellent, and easy to understand. Audio quality was top tier (thank you for that). Code was easy to follow, except Im only guessing that python does automagic memoization? I'm not a python guy. Hope you do many more!
Yep, @cache decorator does that to any function. I liked using that because
1. Recurrence relation is the core idea, manual memoization takes away from the elegance and simplicity and takes up time and kinda distracts from the main point
2. Manual Memoization isn't hard at all. It's just kind of annoying and there's also plenty of examples out there for that
3. When I don't have @cache (which is most of the time since I mainly use C++), I almost always implement it iteratively anyways. Iterative is actually very easy, given you can get the recurrence relation and I'll cover that in the next one
Banger out of nowhere. Thanks for the guidance, though in general you're approach comes with deliberate practice. (Easier for some than others off the bat)
Very good video.
I got a google thing in my gmail and I am not as acquainted with leetcode style problems as I should be. I will do the notetaking methods next time I get the chance to do coding problems. Having all the info right there and breaking it down live seems like a good thing to do. Thank you!
Never heard of dynamic programming before, have been doing dynamic programming since the start
You got one video up but this is so good I'm subscribing now lol
I love this video in more ways than you can count
Maybe I can use dynamic programming to figure it out, but I'll skip thinking about that and just take the compliment :) Glad you enjoyed it!
I learned coding after learning allot of math and also the idea of induction. From a thinking pattern i found it extremely similar, so idk if this holds for anyone else but personally i think if you wanna improve you DP skills you should also just try some induction problems on paper.
Great video thank you! My only question is, is the cache decorator even allowed in interviews? I feel like that's something they'd get all fussy about.
depends on the interviewer, but yeah you should know how to memoize it yourself just in case. I didn't show it in this video because
1. it's not that complicated and there are a ton of existing tutorials on it
2. I wanted to spend more time on building the recurrence relations and doing the time complexity analysis, which are the actual difficult parts of dp that don't get as much attention