5 Simple Steps for Solving Dynamic Programming Problems

[@balkiskaroui882]

Thank you for teaching me in 20 minutes what my professor could not explain in 2 hours , please keep making content !

[@theja63]

Why are professors so bad at teaching such fundamental concepts. I feel like they should also grind leetcode to get teaching jobs lol

[@adg1450]

smart != good teaching

[@proloycodes]

im deaf, and i got a hearing aid and i was told to practice hearing through my hearing aid. so i tried hearing with the closed captions on other videos in other channels and they did not make any sense to my brain. but when i tried yours, i could at least understand some of what you are saying. so thank you for giving me a start by enunciating the words properly. *hugs*

[@williamchan142]

I'm deaf, too. The caption and description in video are very clearly. It's a nice channel for me to learn coding.

[@Bharath-y5j]

@@williamchan142 may god bless you all.

[@airmanfair]

Press F to pay respects to all the people out there that chose the wrong subproblem definition during an interview.

[@ArabicNameGuy]

ف

[@agtugo9197]

F to myself.

[@thux2828]

Wait? DP problems come up in interviews a lot?

[@verdikapuku2596]

@@thux2828 Yes. FAANG companies love to ask the hardest questions. Typically that means DP, Graph, and Tree algo problems

[@vlinkin22]

This is pure gold, someone please give this guy a medal !

[@yangweiyili2514]

I can't thank you more for this video! Most videos out there put a lot of efforts explaining how to solve a dynamic problem with recursion, memoization, bottom-up yadayada... But for me, the most challenging part is figure out what on the earth the problem wants me to do! Your five steps really point out a promising pattern that I can build my own thinking process with. Thank you!

[@vishwasrchonu7134]

Bro, he complicated stuff even more. How is everyone in the comments complimenting him?

[@khadijah9010]

Who knows, this video is horrible and people definitely didn't understand crap. I came up with a solution rather quickly, especially because i have answered a similar problem a few days ago, then he kept talking and talking and talking and soon i found out he is a complete idiot.

[@legenarian6811]

This is finally making me understand DP and how to solve those problems without overcomplicating them i love how you go from explaining the idea to actually fully explaining some code and not just pseudo code

[@travelspurs]

Let's give this guy a real appreciation for visualisation, animation and clear cut explanation. Probably the best on this topic on KZbin ❤️

[@koober_]

Unlike most of the other DP videos out there, this one goes into both simple (yet non-trivial) and challenging examples, which are way more likely to be seen in an interview setting instead of problems like Fibonacci, which are beaten to death. The animation is great and the use of DAGs for visualization really helps things click. I'm genuinely surprised I haven't seen most other resources explicitly mention this DAG-based way of thinking about DP problems before, because it makes it infinitely easier to identify subproblems and their relationships (which was my main roadblock for getting to a DP solution, and likely is for others as well). Keep up the great work and I'll be sure to support you in the future!

[@Reducible]

Thanks for the awesome comment and appreciate the support. I totally agree with everything you said. My main motivation was to find problems that I felt were at a level of difficulty where it requires some real problem solving beyond an example like Fibonacci which I feel is so fundamental that it's not even instructive. The best way to learn and understand DP in my experience is to actually go head first into applying the ideas of finding and solving subproblems in scenarios where the subproblems are a little less clear. And yeah about the DAG relationship, I wanted to make sure I brought that up since in a way, all dynamic programming problems are fundamentally DAG problems. This is mostly just my opinion but I don't feel like a discussion on dynamic programming is complete without mentioning the relationship with DAG's. It's just too fundamental to the core of DP.

[@user-zo9ye6de5e]

@@Reducible there is a problem of finding largest area in a histogram ....i did that in a white page using DAG ....it actually worked but now i got stuck at code implementation...can u plz make a video on that problem and solve it using DAG

[@ratinhoembondeiro646]

​@@ReducibleTo be fair I think if you have started with Fibo example and kept the rest of the video it would have been even better. In the sense, as Fibo is a very trivial example the concept of DP would have been assimilated first in an easier way. Then you can digest easily the more difficult examples. This applies specially for those who watch you vids but are a little bit older who take time to assimilate things. Like in my case, I haven't done algorithms since uni. But still the video is still helpful and nicely done :)

[@YuvrajRaghuvanshiS]

Visualizing it as a DAG is such a nice new trick up my hat, thanks for this.

[@yemam4156]

I took algorithms course 2 years ago, and I didn't understand DP, and just memorized it to pass the exam. Now I understand it, thanks you bro ❤

[@williambertolasi1055]

I love this method to explain. Good job! You have mixed the math reasoning and the practical implementation in an ordered and logical way.

[@sthitaprajnapriyadarshan1740]

You are an absolute genius. You are a mathematician , a scientist , an artist and a teacher

[@tristandam8026]

Wow, you’re gonna blow up dude. These animations are insanely good for learning. Amazing work

[@linchen1756]

I really like how your explain and visualize the problem for us. Really appreciate your work. Looking forward to learning more concepts from your video

[@tiffanyk2743]

This is probably the best video about Dynamic Programming I've seen on KZbin, it covers everything from idea to code and I usually have struggles reading the math but the animation really helped break down what's going on. Keep it up, would love to see more examples! Would you ever plan to make object oriented programming videos in the future?

[@Reducible]

Hey Tiffany, thank you for the awesome comment! There are tons of dynamic programming examples so in the future I could see myself making a video on another challenging problem. For OOP, I haven't really thought about that topic -- maybe? My initial thoughts though are that there may not be too many compelling animations for OOP problems since it's more about code design. The video topics that are usually the best are ones where there is some motivating concept and overarching connection like there is with dynamic programming problems. But who knows, maybe there are some interesting problems in that area -- feel free to let me know if you think of any!

[@shariharan2002]

@@Reducible I dont much about OOP. but i have recently come across this topic in discrete math known as Group theory. its a part of abstract algebra. There is a book known as visual group theory and professor macauley uses this in a yt playlist as a reference. Would it be possible to make a video on that??? since many people find it difficult to read that book but i am sure with your animation skills etc you can bring the entire 300 pages of content into 20 mins. The visuals and example connecting discrete math and chemistry architecture rubik s cube are already there. Some highly skilled people like you only can combine it for the audience. Hope this idea is a good enough one for you to ponder about. Thanks for your awesome video collection. I think you and the author of visual group theory book share the same objective : promote intuituivity first then rigorousness. Thanks a lot!!!!!

[@ShivamJha00]

You need to watch more then

[@khadijah9010]

No it is not, are you a bot? This video is horrible.

[@tiffanyk2743]

@@khadijah9010 why is it horrible, 4 years ago there was no neetcode or anyone else

[@sumanth_]

You're one of the most underrated channel out there. You deserve more and more recognition. Video is great 🙌🙌 I've even recommended it to my friends

[@antonkot6250]

One of the best I watched on this topic!

[@poshakj]

The Best part is you made us think through the process and how to break down a problem. Amazing work.

[@hassanosamakandil8004]

I don't usually comment on videos but man this is the best explanation for a programming concept that I've ever seen on KZbin

[@ogunitracy]

You sir, are a wonderful person and I want you to know that you have changed someone's life today.

[@FoxInFlame]

This is such a great channel, but man, you need to invest in a better microphone...

[@anirudhsilverking5761]

Agreed, he's literally shouting at the mic.

[@Reducible]

Yeah, mistakes were made ... I honestly didn't even realize it was so bad until I got several comments about it. Sorry about that -- I overhauled my old setup and have now actually learned about how to get good audio so I'm hoping it's better in the future. My newest video has no such complaints so hopefully it's better and will continue to improve.

[@FoxInFlame]

@@Reducible That's alright, everyone learns as they go. Keep up your good work!

[@theralf6454]

I agree!

[@123akash121]

@@Reducible i mean your content quality is great, just need a better mic

[@dnagal7816]

Love this video! Really easy to understand and content is professional. Looking forward to more videos from you.

[@Reducible]

Thank you! ;)

[@hlibprishchepov322]

Ага даже я все понимаю)))

[@FrezoreR]

I really like the way you both explain and visualize DP. Especially the visualization part.

[@dinkleberg794]

I have never thought to visualize DP as a DAG but it makes so much sense!

[@frankh1210]

Thank you for this amazing video! Here is some Julia code that corresponds to 7:50 function lis(A) n = length(A) L = fill(1, n) for i in 1:n subproblems = [ L[k] for k in 1:i if A[k] < A[i] ] push!(subproblems, 0) L[i] = 1 + maximum(subproblems) end push!(L, 0) return maximum(L) end

[@valdiviesoercos]

Awesome

[@chaoticmind-z]

One of the best computer science explanations on the KZbin!!

[@MimiKe_]

Thank you for this video. Using a directed graph as a visual is very helpful, and I don't recall it ever coming up as a strategy in my studies.

[@sid6645]

Beautiful video. Never really thought that directed graphs could be this useful in DP!

[@danielvinicius4906]

Amazing Video! Thanks for subtitles, I'm a non native and your pronunciation is perfect and some words I did not knew I could read the subtitles so I could understand your video perfectly, your way of explain things is wonderful!

[@hberry69]

Wish I could have found this channel earlier this semester when I started my algorithms and data structures class. This would have helped a ton.

[@TheTessatje123]

Thanks so much! I like how you 11:13 provide a visualization of the approach and 16:42 go through the implementation. I haven't seen any video describing DP like this!

[@chaitanyalal5626]

I was looking for something like this which explains how to solve dynamic programming step by step rather than just solving questions. This video helped me in a better understanding of dynamic programming than ever before.

[@dylanclements1875]

Thank you for the video. Really pointed me in the right direction as to how to approach DP.

[@damianpatel2794]

The code tracing for the box stacking problem was amazing!

[@XzcutioneR2]

This was super cool! It helped me understand dynamic problems a bit better. I'm guessing it'll still be a lot of work but this is a great start. I went through this video in chunks and spent time thinking about the steps and the problems at hand. Here's to hoping I won't be entirely clueless when practicing dynamic programming on leetcode from now on.

[@gideonbonsu5264]

The DAG bit is fascinating! Thank you!

[@mohamednawar6496]

Amazing and intuitive explanation. Great work!

[@Blowyourspot747]

Best channel I have ever seen as a dev. So amazing and soothing at explaining concepts.

[@Vortex-qb2se]

Honestly, dynamic programming is so easy to me. The hard part is recognizing that it is a dynamic programming problem

[@tejakommuru4716]

wow this is so good and at the end i did understand most part and all i need is some hands on practise. thanks for the video

[@elvis0305]

The explanation on the thinking process is really good !

[@anmolabhayjain9721]

I am definitely sharing this video with my friends and so should everyone else!! Thanks for the amazing tutorial.

[@aniketpriyadarshi2801]

Your question were so interesting. I loved those problems seriously. Thanks for this video very very much.

[@strawberriesandcream2863]

thanks for this video!! i've really been struggling with DP while doing interview prep

[@linminhtoo]

Great video to refresh the most reliable approach to solving DP problems! (am an engineer in AI industry). One thing to add, is that at 16:03 when checking if boxes[j] can be stacked on box, we can break the for loop once we meet the first boxes[j] that is too big, because we had sorted the list of boxes by the criteria (length). This means that the remaining boxes[j] in the list will all also be too big. This will make it a little bit more efficient :) (though it won't change the time complexity).

[@SaurabhKumar-rd2ll]

What do you mean by too big. You should also consider length is sorted but not breadth. So we should check every box of Max height.

[@jduckkk_]

Thank you so much for generalizing such a complex problem in such an way that is so easy to understand. Keep up the great work!

[@saurav0203srivastav]

I literally love this video. This video is perfect. Everything about this video, the explanation, the animation everything. I cant thank you enough for this.

[@gs4207]

**A shift in perspective is what sometimes makes solving hard problems approachable **

[@srividyakrishnakumar6895]

I thought 3b1b started a channel for Computer Science until I heard your voice. Great content. This channel deserves so much more recognition. Thanks! Keep making more videos!! Hope you make more videos on Graph Theory, Backtracking, Recursion, and some of the interesting topics in CS.

[@Reducible]

Thanks for the awesome comment. There is some really awesome CS topics that I have in the works for future videos so stay tuned!

[@srividyakrishnakumar6895]

@@Reducible Cool, I had subscribed already!

[@shreengul6488]

Oh, does it mean he is the same guy who makes 3b1b vedios?

[@devdutmn9608]

​@@shreengul6488no, he assumed that this person is the person behind 3b1b because of the thumbnail of this video.

[@cat-.-]

Wow, this video is a gemstone. I’m a CS major graduate and I still benefitted from it. The presentation is so clear I think it helped me to understand it better now than I did in college!!! Huge fan of the 3b1b visuals too. Did he help you set this up? Great job anyways!

[@raynei]

they use the same animation software I'm pretty sure

[@johnmanardiii3308]

Its a library called manim! Its pretty easy to get started with.

[@TCErnesto]

Dynamic Programming: the idea of solving a problem by first identifying and solving subproblems, and then bringing these subproblems together to solve the larger problem. 1. Visualize Examples: a common model in DP is the directed acyclic graph (DAG). 2. Find appropriate subproblems: think about the start and the end of a subsequence. 3. Find relationships between subproblems: 1. What subproblems are needed to solve a particular subproblem P? Go back in the DAG. 2. How to use these needed subproblems to solve P? Use the solutions of the subproblems as a partial solution of P. Start coming up with the recurrence relation. 4. Generalize the relationship: 5. Implement by solving subproblems in the right order:

[@DaveYognaught62]

Thank you, this video really explained what Dynamic Time Warping is actually doing

[@somdebsar7378]

This same problem i applied to weighted jobs which kind of looks like same and get solved, while i was looking for this problem KZbin suggested me this 😁😁, thanks a lot 👍

[@yasinghoreshi4956]

thank you... you are one of the best teachers in the world

[@standupCoding]

The best thing is that you don't mix up memoization and dynamic programming. It is really very common, not just on KZbin tutorials, but even in colleges!

[@Mannershark]

I've developed a couple dynamic programming algorithms on trees and dags. My prof called these 'local functions', as the value at a node only depends on the in-neighbours. (I haven't seen anyone else calling them that though). The interesting features of these are that the running time is easy to determine based on just the computations required at each node, that it can also be applied to undirected graphs if picking an arbitrary root is possible, and by storing the graph in topological order, it's also IO efficient.

[@immagod5285]

The language of Gods

[@taoliu6334]

KZbin recommended your channel to me yesterday. I wish I'd found you earlier! Great explanation and illustration!

[@joerick]

Nice video! Btw, to my ears it sounds like your mic is clipping. If it sounds like this, try reducing your mic gain. It will sound quieter, then you can bring the volume back using an audio effect like limiter or compression.

[@kacy6014]

Bless your heart lol was looking for someone to explain some intuition behind these magical solutions.

[@loganbrown9553]

My solution for the first problem was to organize the data as a tree where you start at the last entry and connect that to all entries which are lower than it and further back and then do that to all the nodes further down. Then, to find the longest path you can effectively just do a depth first search and move through all of the points in the tree until you have the longest path

[@Fake_Disciple]

That’s a brute force method. Not dynamic programming method

[@WizardOfArc]

The DAG tip is super helpful!

[@sridharaddagatla]

I've watched one video of this channel and hit subscribed !!! What an amazing channel. Thank you so much for a clear and simple explanation.

[@adityahpatel]

This is very specific to the problem shown. This cannot be generalized as the common steps for all dynamic programimng problems

[@joshelguapo5563]

Yeah this is a masterclass in how to teach CS. Great job!

[@АльбусДамблодр]

Bro, thank you a lot for this video. Dp problems were always a 'pain in the ass' for me, cause i didn't even know how to start solving them. But this video helped me a lot to understand 2 dp problems and gaved me a pipline how to solve this kind of problems! Really appreciate your work, dude, thanks! Btw this was my first your video. Looking forward to study your whole channel)

[@shariharan2002]

directed acylic graphs and dynamic programming wow!!!!! superb !!!! amazing!!!! i was just bogging around this idea in the morning, but i was not close to it. i was seeing papers related to both dynamic programmig and graphs. being a little weak to dp, I came across your video!!!! wow, the key you have presented is::::::THE GRAPH REPRESENTS ALL VALID SOLUTIONS, not every solution. In mind till now i thought remotely that Dp was somehow computing every solution(including invalid ones)!!!! I know I am totally wrong and I am extremely happy that you were there to correct me. Thanks a lot !!! Thank you very much Reducible!!!!!!!!!!!!! Superb awesome and great work!!!! Thank you again!!!!!!

[@kepler_22b83]

Thnx... Didn't get it at first but it helped a lot once I took a breather to think... Studying more than 8h muddles the mind a little...

[@yogeshvishnole1264]

Super sir , it is one of the most understandable explanation of dynamic programming.

[@Daniel-eu5ny]

Thank you for this video. This really helped me unterstanding dynamic programming for an exam which will be in 2 days

[@dorondavid4698]

With your explanation, I actually find the topic interesting now as well! Great vid!

[@JacemHagui]

This video helped me code the solution in c, the code finally works and I'm so relieved. Thanks a lot, love your other videos a lot as well, first one i watched was the one about recursion and it's a gem !

[@VietnamSteven]

You deserve infinite amount of likes! Thank you!

[@igorku7369]

Explanation from 8:11 to 8:26 - broke my head. The guy knows what he is talking about, but his explanation is too academic and hard to comprehend for beginners. Will try to come back to this video in another year...

[@jaykantbhaau8618]

Your videos are much helpful for learning the contents. Please upload more such contents. I recommended it to my friends.

[@ArgumentumAdHominem]

It seems from the comments that the video has received quite a bit of praise. While the visualizations are top notch, I am concerned about the structure of the material. More precisely, I expect that the omission of computational complexity would severely hurt the otherwise excellent learning material. Omitting complexity leaves an insurmountable gap in creating an understanding of the necessity of dynamic programming. I do understand the desire to simplify the learning material to reach a wider audience, but this topic is already sufficiently involved, and those capable of comprehending it surely would have at least heard about the term. It is really not that much overhead to show the viewer that (1) the naive solution to LIS (picking all possible combinations of sequences and checking if they are valid and longest) requires a lot of operations (exponential in problem size), whereas (2) the proposed algorithm reduces the complexity to quadratic, which is an extreme improvement. Further, it is instructive to discuss why the proposed algorithm happens to be better than the naive one.

[@tanmaybhagwat3650]

This video provides such great clarity about the steps and logic behind formulating a solution. Keep up the good work!

[@jdhao6498]

I find the explanations and animations extremely clear. Thanks for making this video!

[@jarmanbrar4114]

Such a great video again. You deserve much more recognition.

[@haitu8896]

I really like the way you explained, it's clean and clear, it's much better than any course about DP in computer science class I took. Visualization DP problem as graph and finding sub-problem are great points, I just love it.

[@ernsttech5255]

Thanks for your amazing content, quick question the purple box (1,2,2) and orange one (2,3,2) the heights are both 2 and the constraints is Li < Lj and Wi < Wj, 2 is not < 2. Please advice

[@christoffermedc]

i reacted at this as well as i was implementing the problem, i think the constraint should have bin specified: Li

[@ShadArfMohammed]

Thanks for investing a lot of time in making the animation. I think you need to consider your teaching methodology as well, this video makes the topic much harder than it really is.

[@arminmarka1239]

kindly continue making these videos

[@virajgoyanka5227]

90K soon !

[@justinwhite2725]

2:18 before seeing the 'right' solution, what I did to find it was to find the smallest number on the left and the largest number on the right. It won't work for all sequences but the longest sequence has to at least be in there somewhere.

[@stefanborek7101]

Great video! Watching with my whole college dorm. 🐍💪✨

[@TsArun-qw6xn]

This video blew my mind on how to break down problems! Most informative video on DP. I have seen! Thank you for making this.

[@sahil-nz7vk]

Great video! Really liked the smooth animations!

[@pb-hx2hv]

Great video. Visualization as Graph is super helpful!

[@abhirup619]

best explanantion of this concept and also the most beauiful in any book or video ever!!!!

[@chenvili]

Loved the video!!! It really helped me in understanding the subject.

[@they_call_me_noob]

Wow! The best explanation ever! Love it! Thank You

[@pritam1366]

man can you do more videos on dynamic programming , it helps a lot.

[@hima4411]

did not find a better explanation for dynamic programming,take a bow!!!

[@abyss2200]

All your content is very nice and so helpful and the way you add the background music is a good idea 😉👍

[@smrtfasizmu6161]

These feel like math problems from math competitions back in middleschool, except it is math with computer programming. Fun problems to think about and solve.

[@XzcutioneR2]

t1 = [2, 3, 1, 4, 5, 7, 6, 8, 9] def lis(a): l = [[k] for k in range(len(a))] for i in range(len(a)): subproblems = [l[n] for n in range(i) if a[n] < a[i]] l[i] = max(subproblems, key=lambda x: len(x), default=[]) + l[i] return [a[i] for i in max(l, key=lambda x: len(x))] print(lis(t1)) This is how I kept track of the entire subsequence. But I'm guessing an interviewer would probably point out the space complexity of this.

[@andrewtracey7016]

Great video! Very clear explanations and the visuals were so helpful.

[@vijay6877]

it feels so good to like this video. Thank you so much for all the insight.

[@freedom_aint_free]

Amazing video! This video turned out so good, that I'd like to encourage you to do the voice over again: because your MIC was clipping as the input gain was probably too loud it deserves a crystal clean audio to go along with it!

[@ImposterBraum]

This is so interesting to work through on my own, thanks for the video!