These are good and makes me realize what a great CS curriculum I had that covered all 5 of these lol. I would also study 6. DFS + memoization (Longest Increasing Path in a Matrix, Path Sum III) 7. Backtracking + memoization (Regex/Wildcard, Partition to K Equal Sum Subsets) 8. State Machine (Best Time to Buy & Sell Stock variations)
DP = recursion + memoization. Then, if you want to memoize using an array instead of a hash map, you can optimize that after. So it's no harder than recursion. But DP often uses a variable number of subproblems, while more straightforward recursions use only one or two subproblems.
The issue is that recursion usually results in exceeding time limit or memory complexity. It's almost as if leetcode expects a bottom up solution. Recursion+memoization works for the simpler problems, but definitely not for problem like 0/1 knapsack
@@_PranavDesai Recursion + memoization works for *all* dynamic programming problems. Look for a leetcode post by chrisTris on 0/1 knapsack and dynamic programming.
some real quality content here. interview material is usually bloated with edgy-cleverish stuff, not structured according to problem's domain of knowledge and not prioritized correctly. you, sir, have managed to sort all that out. thank 🤜🤛
I'm not confident with dp problems. But this spreadsheet is awesome!! Thank you as always. And congrats you've gained 10k subscribers so far :) You deserve more.
Love the videos. SMALL EDIT: For the “Unbounded Knapsack”, we do not need 2D array. We only need to know MIN(coinsUsed) at each position. Since we can use any coin at each position, we do not need to track type of coins used.
Your videos are really helpful. Just a suggestion, it would be really nice if you could create a video on when we should do backtracking vs dynamic programming. As some seems to fall on both with different runtime and people use different solutions
actually, i think both backtracking and dp is bruteforce which try all combination, but if one can build an optimal structure and a DAG , then definitely we should use dp to reduce from exponential time (backtracking/dfs)
I want to thank Neetcode. The videos were great resource to learn coding and crack tech interviews. I'm very thankful to this channel. Hope your channel grows more and more. ❤️
I don't think 0/1 in 0/1 Knapsack refer to finite/infinite number of the item - its more about if the item put in the knapsack can be fractional or not. 0/1 means either it exists in the knapsack or it does not - in fractional knapsack, you can pick fraction of some item as well -- which would be represented as .someDecimalValue, not 0/1.
Guy, you really helped me a lot! After watching Climbing Stairs video I did solve Maximum Alternating Subsequence Sum problem not only using DP but using bottom up approach!
This style of videos is very informative. It helps to structure and categorize the information related to DP problems and allows to come to the solution faster.
This is perfect. Thank you. Can you please make similar lists for other topics as well? That will be extremely helpful because while solving the problem it's good to have an idea about general approach you'll be following..
Can you please make videos on fundamental DP questions (such as the ones you listed in this video) and solve them with multiple solutions describing how you build intuition to build the Brute Force way and optimized it in Top-Bottom/Bottom-Up fashion and finally optimized it with constant space. I understand you have explained the approaches in a your videos but can you go in a bit more depth as to how you came up with the Brute Force approach and how you thought that I can optimize it in this way. Your videos have been of great help, Thank you.
From your Dynamic Programming Patterns sheet, I think Fibonacci Number is kind of Linear DP problem whereas House Robber is more of a Decision Making kind of problem so they should not be falling in the same bucket in case you are categorizing them. Any thoughts?
This is probably a long shot but can someone explain how the palindrome solutions are DP? Ive seen the individual problem solutions and they all use the expand from center trick which isn't really memoization thus not really DP(at least how I understand it). On LC, I see solutions of more standard DP approaches that use a 2d array to memoize a string from any 2 start&end points.
Do you think it okay to solve DP problems with recursion with memoization? It's often much easier for me to conceptualize the recursive implementation than the iterative one. Theoretically it should be the same, but with the use of the call stack.
I'm just wondering what your adivce would be on how much and what algorithms in terms of coding I should know if I wanna apply for Amazon data scientist role? Thank you!
Thanks a lot ! But after seeing this video i was trying to solve the 1/0 knapsack problem type - equal partition based on tabular method rather than your solution video of the same. Unfortunately I am not able to solve the same can you please create video how tabular method works for the same question ?
Mr. Neet Code. I wanna make a request for 935. Knight Dialer if you struggle to choose a question. it is asked by Facebook and there is no explanation on youtube.
You seem to make things harder with explanation and graphs. You should explain with a datastructure, like in an array or hashmap, etc or say a for-loop etc for context to make it easier to understand.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
These are good and makes me realize what a great CS curriculum I had that covered all 5 of these lol. I would also study
6. DFS + memoization (Longest Increasing Path in a Matrix, Path Sum III)
7. Backtracking + memoization (Regex/Wildcard, Partition to K Equal Sum Subsets)
8. State Machine (Best Time to Buy & Sell Stock variations)
are dfs + memoization & backtracking + memoization the same? at least in neetcode's videos, he uses dfs algo for any backtracking problem
@@dj1984x DFS is not just backtracking, but backtracking is always DFS.
what are state machine problems and how are they different from any other dp problem can you explain the fundamentals briefly
This channel is such a great find. I just wish there were more videos haha
DP = recursion + memoization. Then, if you want to memoize using an array instead of a hash map, you can optimize that after. So it's no harder than recursion. But DP often uses a variable number of subproblems, while more straightforward recursions use only one or two subproblems.
The issue is that recursion usually results in exceeding time limit or memory complexity. It's almost as if leetcode expects a bottom up solution. Recursion+memoization works for the simpler problems, but definitely not for problem like 0/1 knapsack
@@_PranavDesai Recursion + memoization works for *all* dynamic programming problems. Look for a leetcode post by chrisTris on 0/1 knapsack and dynamic programming.
Tabulation is also DP and it is not recursive at all
@@wojak6793 Please re-read my comment, thanks.
some real quality content here.
interview material is usually bloated with edgy-cleverish stuff, not structured according to problem's domain of knowledge and not prioritized correctly.
you, sir, have managed to sort all that out.
thank 🤜🤛
I'm not confident with dp problems. But this spreadsheet is awesome!! Thank you as always. And congrats you've gained 10k subscribers so far :) You deserve more.
damn so he got 200k within year
damnnn 250k now
516k now
another 30k in a month dayum@@liz.1328
@@liz.1328 700k+ now
Love the videos. SMALL EDIT: For the “Unbounded Knapsack”, we do not need 2D array. We only need to know MIN(coinsUsed) at each position. Since we can use any coin at each position, we do not need to track type of coins used.
The feeling that the athor somehow bullshittin us huh ? 😀
Your videos are really helpful. Just a suggestion, it would be really nice if you could create a video on when we should do backtracking vs dynamic programming. As some seems to fall on both with different runtime and people use different solutions
actually, i think both backtracking and dp is bruteforce which try all combination, but if one can build an optimal structure and a DAG , then definitely we should use dp to reduce from exponential time (backtracking/dfs)
We use dp when their are overlapping sub-problems, here in this problem their is not any sub-problem(part of problem we have already solved)
I want to thank Neetcode. The videos were great resource to learn coding and crack tech interviews. I'm very thankful to this channel. Hope your channel grows more and more. ❤️
I don't think 0/1 in 0/1 Knapsack refer to finite/infinite number of the item - its more about if the item put in the knapsack can be fractional or not. 0/1 means either it exists in the knapsack or it does not - in fractional knapsack, you can pick fraction of some item as well -- which would be represented as .someDecimalValue, not 0/1.
Yes correct, this falls in the category of unbounded knapsack where you are not confined to use the element only once.
Guy, you really helped me a lot! After watching Climbing Stairs video I did solve Maximum Alternating Subsequence Sum problem not only using DP but using bottom up approach!
The best Python Leetcode problem solver. Love u brother ❤️
This style of videos is very informative. It helps to structure and categorize the information related to DP problems and allows to come to the solution faster.
This is perfect. Thank you.
Can you please make similar lists for other topics as well? That will be extremely helpful because while solving the problem it's good to have an idea about general approach you'll be following..
This is truly life saving! Please make more of this type of videos for other topics.
Thank you @Neetcode, you are changing people's lives
Easily the best LC channel, thank you :)
Thank you! This is so helpful! I look forward to more of this type pf high level overview :)
The way you explain CS is awesome, bro! Keep doing the good job!
Thanks!
Thank you so much, I really appreciate it! 😊
Are you spying on me? This is literally what I was searching for! xD
not he, it is goo...
The best Leetcode channel ever
Could you please add the 'Matrix Chain Multiplication' category to this sheet?
The palindrome checking method so helpful!
Very Important for understanding core concepts of dynamic programming.
After i suggested neetcode to my friend’s
My friends: should we bow ?
Me: Yeah, he’s a king.
Really love the content, keep going 🔥
Thanks for this spreadsheet.
Can you please make videos on fundamental DP questions (such as the ones you listed in this video) and solve them with multiple solutions describing how you build intuition to build the Brute Force way and optimized it in Top-Bottom/Bottom-Up fashion and finally optimized it with constant space.
I understand you have explained the approaches in a your videos but can you go in a bit more depth as to how you came up with the Brute Force approach and how you thought that I can optimize it in this way.
Your videos have been of great help, Thank you.
Brilliant explanation, your videos are extremely helpful, thank you for doing all the good work :)
I've been doing DP for a while so not exactly a beginner, but this is still helpful way to see things
Great stuff! I have learned a lot from your videos. Please do more of these!
very clear explanation. good job NeetCode. keep up to date your videos . thanks
this is so AWESOME!!! thanks for sharing your knowledge :)
You are just saviour in my battle-hour!
From your Dynamic Programming Patterns sheet, I think Fibonacci Number is kind of Linear DP problem whereas House Robber is more of a Decision Making kind of problem so they should not be falling in the same bucket in case you are categorizing them. Any thoughts?
I think this is really good, though I think we should motivate recursion way more. The grid is fine, but it makes more sense doing that
Thanks for sharing this approach.
I think Longest Increasing Subsequences (LIS) type problems deserve its own category ... Also Maximum Sum Subarray (Kadanes Algo)
Yeah LIS is pretty big, you have problems like Russian Doll Envelopes & Box Stacking.
Please make and share more videos / spreadsheets like this
They are really helpful for practice 🙏
Finally I finish all the exercises listed in the dp spreadsheet. It has been a lot of help, thank u. wish there are more summary videos like this.
This is probably a long shot but can someone explain how the palindrome solutions are DP? Ive seen the individual problem solutions and they all use the expand from center trick which isn't really memoization thus not really DP(at least how I understand it). On LC, I see solutions of more standard DP approaches that use a 2d array to memoize a string from any 2 start&end points.
Looking forward for this
amazing, please keep doing this wonderful work.
Thanks a lot! You're the best
Just what I was looking for, ty! Just a thought maybe you could extend this to other types of leetcode problems?
Good idea, I definitely will try to work on that!
Awesome video! thank you so much
you are the best teacher
Really helpful, thank you very much
What's the whiteboarding software? Do you just use a mouse or some sort of pen tablet?
U are just awesome. thanks a lot
Do you think it okay to solve DP problems with recursion with memoization? It's often much easier for me to conceptualize the recursive implementation than the iterative one.
Theoretically it should be the same, but with the use of the call stack.
It's slower but it's ok.
You're my hero.
very good video! thanks so much.
What does for beginners mean? Are there more patterns?
man i just so love you!!
what is the device / software thatdraws on the screen? very interesting
Ace video, mate.
I'm just wondering what your adivce would be on how much and what algorithms in terms of coding I should know if I wanna apply for Amazon data scientist role? Thank you!
You got the subscriber💕💕
Can you make a video on Critical connections?
thx for your work!
Thank you neetcode
you are the god !! thank you
Curious what device and software you use to present like this.
why you don't use Binet equation for fibonacci ?
Great Video!!!!, are you a faang employee??
Fantastic video
Thanks a lot ! But after seeing this video i was trying to solve the 1/0 knapsack problem type - equal partition based on tabular method rather than your solution video of the same. Unfortunately I am not able to solve the same can you please create video how tabular method works for the same question ?
Thanks alot . Too good....!!!
I am not unable to convert memoisation to dp how to do it ?
Could you please do a video on "Longest Palindromic Subsequence"?
very clear
Omg ily so much. I think you are missing Matrix Chain Multiplication pattern and DP on trees. But still ILY!!
Another category that might be helpful here is probably matrix/maze problems
how to get the spreedsheet
Thanks. You just made it clear. fear---;
You're one the rare examples of someone with an American accent who pronounces "new" like "nyoo" instead of "noo"
Love it~
Low-key thanks.
Mr. Neet Code. I wanna make a request for 935. Knight Dialer if you struggle to choose a question. it is asked by Facebook and there is no explanation on youtube.
Is this the same guy who posts daily dose of internet?
Where is the speadsheet?
Did you check the description?
@@NeetCode oops thanks
can i get the spreedsheet?
Link should be in the description (let me know if its not working)
Amazing
KING
why you don't put this video a the first place in this dp series
I would definitely become a patron but currently I am struggling financially. If I get a job this year would make a generous donation.
right
Can u please reduce the number of adds it's too much irritating
5:25
Binary tree cameras leetcode
I feel so stupid watching these videos.
You seem to make things harder with explanation and graphs. You should explain with a datastructure, like in an array or hashmap, etc or say a for-loop etc for context to make it easier to understand.
the "right?" is pretty distracting
n33tc0de, I love u bruh
Thanks!
Thank you so much Alex!!!
Thanks!
Thanks!
Thanks!
Thanks!