When is the 4th step not possible I wonder? Maybe when the DP transition formula involves variable time step difference or something like that (i.e. something more dynamic that dp[i-1] and dp[i-2])
@@iiJDSiiThere are tons of problems where the space cannot be optimised to lower dimensions. It is basically when the value of a paticular entry in dp table doesnt depend on a predictable element, or maybe different values depend on different entries spanning the entire dp table. In the fibo case, we could already say that the value at the current position depends on just the last 2, so we could optimise the dimension down to 0.
very good summary of the step by step optimisation of DP problems, but it is hard for new learner to understand these 4 steps without a full blown explanation.
Great video demonstrating progressive code refinement. Still not sure if the first step should be called "recursive backtracking". As discussed in previous video, think this is just "naïve recursion".
I find that top-down solutions are easier to understand due to the decision tree nature of the solution as opposed to the bottom-up with dp that is sometimes harder to find the transition step.
The trick I use is to first create the recursive approach to find what parameters need to get passed to the method that changes with each call.. those are your tabular row and columns. Then I try to find out what's the ending condition to the recursive function given minimum number of input (i write these two aside). Finally i write down what needs to be computed and returned from the recursive function. Thats the stuff you store in table. Then with these 3 information i try to reconstruct the top down table (which works in almost all cases leaving a few very difficult problems where I cant get my head around it even via recursion lol)
Within the last year, I rewrote a large algo involving many function calls that would recurse upon itself. It was taking a long time, and I knew the recursion was contributing to the duration, so refactoring to "bottom-up" would speed it up. It took some time to wrap my head around, but after that exercise, I now find the bottom-up approach more intuitive somehow. Basically, what it boiled down to in my case was keeping track of each "recursive" call (just a while loop now) by throwing the next set of arguments into my own "call stack." The base case simply didn't push any set of arguments onto the stack, so the loop ends when there is nothing left to work on.
What do DP do?: It actually selects one best solution from all the possibilities And the possibilities are reduced by reusing/Memorization/Tabulation,(when there are 2 or more subproblems overlapping then we can avoid those subproblems and substitute from the memorization 😎)
What's complicated about DP IMO is figuring out what do the output depend on in such a way that it's memoizable, when facing new and complicated problems, It's not obvious at all
Hey Gregg, I'd love to see a deep dive into DP. Most importantly, I'd like to know how I can convert my naive approach progress from top-down to bottom-up to true dp solutions. Thanks in advance.
I’ve seen most jobs wanting the degree in computer science, did you learn on your own or did you get your degree? I’m asking because I’m interesting in learning this skill!
I think the memo dict would be a new one for each stack frame. I might be wrong. You are better off using lru_cache from functools or make the dict global
The memo dict was instantiated inside fib(n) and its reference was stored in the name "memo"; The f(n) function calls itself, not fib(n). Python uses the LEGB (Local, Enclosing, Global, Built-in) rule for name resolution, when it look up the name "memo" within f(n) and find out that it's not there, it will look for that name in the enclosing scope aka fib(n). Since there are only lookups and no assignment to the name "memo" within f(n), the "memo" within f(n) is the essentially the same as "memo" in fib(n).
Hi! I am a beginner in DSA and can only do easy array and string questions. How to start learning DP and Graph? And from where to learn? Like I need a playlist that explains theory(so i can make notes) + codes If anyone is able to provide any links, much thanks😊
Just think about the years it takes to summarize this classical intro DP problem. Another thing is to distinguish greedy and DP because they both ask for min/max and get results based on the previous results. So, I would stop at the Top-down DP and draw some trees due to @cache. I would use return at the leaf node.
@@GregHogg is that because it starts at f(6) and basically does a trickle down tree (horrible description) and then when it gets to the default cases of 0 and 1 it goes back up the tree to the actual f(6)? Sorry just trying to work through the terminology, i'm new to studying actual algorithms with programming
hey @GregHogg I am you huge fan! And I use algo for learning programming. Could you also please suggest me some good books i should use to learn logical programming? I dont want a book for learning a language... just the logic behind prograaming. I would be hughely grateful. Much love from India
hi guys, im new in programming. on the 2nd approach, even though it results better in time complexity (lowered to O(n) ), doesn't it affect performance on the space complexity because it does memoization?
Let's take a moment to think about this-you’re working extremely hard and carrying massive student loans, all to land a job at a FAANG company, only to end up making others wealthier. Jeff sends his regards with a big hug.
“No memory dp” should be “Less memory dp” because it’s typically possible to get down from a table to a list or god forbid a 3d array to a table Maybe even call it “Reduced dimensions dp”
You totally missed the point of DP. You can pass just by explaining how you derive the solution and implement bottom up or top down with memo, which ever is easier for you
Dynamic programming shares pretty much nothing in common with data science (although sadly still you might get asked it in an interview), so that's okay haha
Don't worry, i've made many programs in Python and there's been almost no instances where i've needed anything that he is talking about. Just use built in sort() and min()/max(), bisect, "in" operator or if dealing with dataframes using the built in vectorization methods in pandas and etc...... literally don't need to know what he is talking about.
@@GregHogg sure sure, but I can't understand how it is anything different from normal programming where you divide the task into small sub tasks and solve those.
I wrote c#, i don't know if it can be done any other way than just using recursion with a limiting condition without making the code look like gibberish
Personally don’t like this approach I think learning straight the way to dp with an array is the correct way, this is how we’re thought in the University The other are good ways to solve general problems, but not DP ones
I've heard "dynamic programming" so much over the years but had no idea it was just this, which I've been doing for years. I even recently wrote fib in Rust (arbitrarily chose it as a learning exercise) and immediately opted for bottom-up no-memory... because it makes the most sense. I remember first learning fib with recursion back in the day, but that's a pointless application.
60 seconds is a pretty short amount of time to learn 4 algorithms. This is a high level understanding video, it'll likely take more time than this to fully grasp :)
Why solve the problem 4 times? Just write down the DP formulation and then write the code. Also step 4 is just for special cases. You don't know if the solution will depend on a constant number of previous values.
@@TheStrandedAlliance Like I said, when the current value doesn't depend on a constant number of previous values. Or when you don't know which values to maintain in advance. In the simple case of the fibonacci series, you only have to save exactly 2 values regardless of the current step, and you know which ones. In more complex problems you won't know in advance which values to save or how many. So you can't allocate O(1) memory for them and the only way is to maintain the whole table.
@@polycrystallinecandy Can't you just manage a dynamic list then? Also, in the recursive case, the values will just fill up the stack instead anyway, no? That would be pretty bad if you have a huge amount of values (-> stack overflow).
@@TheStrandedAlliance no, because you need to know ahead of time. By the time you get to the iteration where you know which values you should've saved, you've already lost them. You don't have to do recursive, you can do an iterative version (step 3), just save all the values in a table.
Sometimes true. Agreed, you don't actually have to follow these steps if you know what you're doing. I'd argue it's a natural order to solving the problem, understanding it completely, and getting good practice in
precision issues will start to appear, also what if I want it modulo a large prime (like 10^9 + 7) and ask you to find the, for example, 748243191942148th Fibonacci number
Too complex. Just learn the formal dp from Algorithm book. I suggest "Introduction to algorithm III". If there are overlapping subproblems and optimal substructure, then we can use dp. Both top-down and bottom-up dp are tabulation. (This vedio is not right.) Tabulation means memorize the result to calculate everything in only 1 time. Here are the steps to do dp problems: 1. Define the definition of your dp. Ex. dp[i] means the minimum step to reach ith floor. 2. Write down the recursion. Ex. dp[i] = dp[i-1]+dp[i-2] in Fibonacci. 3. Write down boundry conditions. Ex. n = ?, then... Hope this can help someone learning dp. : )
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Read this with ypur dirtiest mind
2 on 1* tutoring.
I think that's why they call it "pair programming". 😉
reported for advertising
Ty for that great DP help. Couldn't do it alone. No matter how much I put into that.
How much money will I need for tutoring from you?
4th step sometimes not possible, but yeah up to 3 definitely.
Yes that's correct
When is the 4th step not possible I wonder? Maybe when the DP transition formula involves variable time step difference or something like that (i.e. something more dynamic that dp[i-1] and dp[i-2])
@@iiJDSiiThere are tons of problems where the space cannot be optimised to lower dimensions. It is basically when the value of a paticular entry in dp table doesnt depend on a predictable element, or maybe different values depend on different entries spanning the entire dp table.
In the fibo case, we could already say that the value at the current position depends on just the last 2, so we could optimise the dimension down to 0.
@@iiJDSii for example: 322. Coin Change
very good summary of the step by step optimisation of DP problems, but it is hard for new learner to understand these 4 steps without a full blown explanation.
I'm just a tradesman and stumbled upon this vid. I have NO idea what's going on but it looks cool
If you would like to learn cs I would recommend w3schools, a coding website.
You know how physical labor makes your body ache, this is the same thing but you're doing it to yourself mentally instead of physically.
It’s torture
but the dopamine after solving a question
With these shorts, i should be able to become a code guru in one hour.
Great video demonstrating progressive code refinement. Still not sure if the first step should be called "recursive backtracking". As discussed in previous video, think this is just "naïve recursion".
I find that top-down solutions are easier to understand due to the decision tree nature of the solution as opposed to the bottom-up with dp that is sometimes harder to find the transition step.
I completely agree 💯
The trick I use is to first create the recursive approach to find what parameters need to get passed to the method that changes with each call.. those are your tabular row and columns. Then I try to find out what's the ending condition to the recursive function given minimum number of input (i write these two aside). Finally i write down what needs to be computed and returned from the recursive function. Thats the stuff you store in table.
Then with these 3 information i try to reconstruct the top down table (which works in almost all cases leaving a few very difficult problems where I cant get my head around it even via recursion lol)
Within the last year, I rewrote a large algo involving many function calls that would recurse upon itself. It was taking a long time, and I knew the recursion was contributing to the duration, so refactoring to "bottom-up" would speed it up. It took some time to wrap my head around, but after that exercise, I now find the bottom-up approach more intuitive somehow. Basically, what it boiled down to in my case was keeping track of each "recursive" call (just a while loop now) by throwing the next set of arguments into my own "call stack." The base case simply didn't push any set of arguments onto the stack, so the loop ends when there is nothing left to work on.
What do DP do?:
It actually selects one best solution from all the possibilities
And the possibilities are reduced by reusing/Memorization/Tabulation,(when there are 2 or more subproblems overlapping then we can avoid those subproblems and substitute from the memorization 😎)
Great tips! What would your tips for nailing down a ZYLYTY code challenge?
What's complicated about DP IMO is figuring out what do the output depend on in such a way that it's memoizable, when facing new and complicated problems, It's not obvious at all
Yes that's definitely the tricky part
Hey Gregg, I'd love to see a deep dive into DP. Most importantly, I'd like to know how I can convert my naive approach progress from top-down to bottom-up to true dp solutions.
Thanks in advance.
Thank you! Yes I am absolutely working on those longer form videos to discuss these topics :)
I am new to DS and I find this really beautiful ❤
I’ve seen most jobs wanting the degree in computer science, did you learn on your own or did you get your degree? I’m asking because I’m interesting in learning this skill!
I think the memo dict would be a new one for each stack frame. I might be wrong. You are better off using lru_cache from functools or make the dict global
I was confused as well. How would it work if each time fib is called, the memo object is reset?
The memo dict was instantiated inside fib(n) and its reference was stored in the name "memo"; The f(n) function calls itself, not fib(n).
Python uses the LEGB (Local, Enclosing, Global, Built-in) rule for name resolution, when it look up the name "memo" within f(n) and find out that it's not there, it will look for that name in the enclosing scope aka fib(n).
Since there are only lookups and no assignment to the name "memo" within f(n), the "memo" within f(n) is the essentially the same as "memo" in fib(n).
You could solve it in O(log(n)). Some say this problem could be solved in O(1), but they need to calculate the square root, and this costs O(log(n)).
🙏 bottom up approach saves me mostly
Hi! I am a beginner in DSA and can only do easy array and string questions.
How to start learning DP and Graph?
And from where to learn?
Like I need a playlist that explains theory(so i can make notes) + codes
If anyone is able to provide any links, much thanks😊
How to do the 4th step in antoher algorithm? For example the knapsack?
It's just about storing exactly what you'd need to store at each time, and this will vary per problem
I don't think that approach is suitable for the knapsack problem. Atleast not for the 0/1 knapsack problem
this is gold thank you
You're super welcome, sorry for the slow response!
For the last option, you didn’t use the i in the for loop?
As a computer science minor, I have no idea what any of that means, but it all looks about right. 👍
I feel like you just summed up one the first lecture on dynamic programming from an old mitocw series
Just think about the years it takes to summarize this classical intro DP problem. Another thing is to distinguish greedy and DP because they both ask for min/max and get results based on the previous results. So, I would stop at the Top-down DP and draw some trees due to @cache. I would use return at the leaf node.
how is example 1 "recursive backtracking" when it just produces the nth number of a fibonacci sequence?
Because it does it through recursive backtracking, or basically, the most brute force thing possible
@@GregHogg is that because it starts at f(6) and basically does a trickle down tree (horrible description) and then when it gets to the default cases of 0 and 1 it goes back up the tree to the actual f(6)? Sorry just trying to work through the terminology, i'm new to studying actual algorithms with programming
No time gotta check labview out then go back to mongodb then back to intune and active directory then cybersecurity
Is it memoization or memoRization?
hey @GregHogg I am you huge fan! And I use algo for learning programming. Could you also please suggest me some good books i should use to learn logical programming? I dont want a book for learning a language... just the logic behind prograaming. I would be hughely grateful.
Much love from India
Thanks
And i must also thank striver.
hi guys, im new in programming. on the 2nd approach, even though it results better in time complexity (lowered to O(n) ), doesn't it affect performance on the space complexity because it does memoization?
Correct. Although we usually care more about time :)
@@GregHogg thank you!
That is a great question to ask during an interview: "Am I constrained by memory?"
Everytime I get asked a DP problem in interviews. I find the lowest time complexity algorithm to find the shortest path out the interview room.
Just throw a HashMap on it
That's step 2 yes
You didn't understand the second step lol
guys, it's a thing Nicolas T. said in one of his videos lol
That's #2😂, it's a dictionary in Python but same exact thing
OMFG, it's an inside joke in the programming community 🙄. No wonder you all don't get it when you watch TH-cam tutorials.
Is 4th step limited to 1-D dynamic programming
?
No it doesn't have to anything with dimensions. It depends on the information we are using for caching
Can u do this in C++
5th solution, solve it on O(ClogN) where C depends on the dp specific recursion
How perfect. 4h@uni vs your smart and small overview explenation. Thx
Why not use a hashmap?
For the memoization?
The ting sound resonated my soul
Good good 😂
I can usually think of a top down approach but not the bottom up
#4 should be optimized space complexity which includes O(1) for 1D DP instead of O(n) and O(n) for 2D DP instead of O(n^2)
You cannot guarantee this unfortunately!
What is considered as DP here!?
I thought I was good with Python until I saw this video
This isn't Python though, it's basic algorithms :)
@@polycrystallinecandy it's definitely python
This video has nothing specific to do with python.
Pretty sure I saw python
@@kakimell101Pretty sure I also saw vscode, doesn't mean it's got anything to do with it
Why is tabulation the way I would’ve done it. It seems the most straightforward
Tabulation is the best!
Yep get your full course for this at code camp
Gernalized an example for whole dp ,hence incorecct
i dont know about the caching thing thanks for telling and explaining
Yeah, pretty interesting stuff! You're very welcome :)
I dint understand 2nd one but other 3 were still understanable
I wonder if people having passed the dynamic-programming tests ever actually used it in their jobs?
They definitely don't 😂
If we want to go little further we can take a look at the Golden ratio
Yeah, why iterate when you can directly compute the result? :)
Let's take a moment to think about this-you’re working extremely hard and carrying massive student loans, all to land a job at a FAANG company, only to end up making others wealthier. Jeff sends his regards with a big hug.
East or West Striver is the best
“No memory dp” should be
“Less memory dp” because it’s typically possible to get down from a table to a list or god forbid a 3d array to a table
Maybe even call it
“Reduced dimensions dp”
You totally missed the point of DP. You can pass just by explaining how you derive the solution and implement bottom up or top down with memo, which ever is easier for you
and 5 step use matrix
I have just started, so didn't understood a word that you said.
thanks man
I started studying programming for data science about two months ago and what h r saying sounds like Chinese to me, am soooo far 😂
Dynamic programming shares pretty much nothing in common with data science (although sadly still you might get asked it in an interview), so that's okay haha
Don't worry, i've made many programs in Python and there's been almost no instances where i've needed anything that he is talking about. Just use built in sort() and min()/max(), bisect, "in" operator or if dealing with dataframes using the built in vectorization methods in pandas and etc...... literally don't need to know what he is talking about.
Step 4 might not be possible for every problem but definitely till tabulation part.
Backtracking solution indeed o(2^n) but there is tighter upper bound
Just for folks. 4th is not greedy approach. It’s still a dp based.
Yes still dp just constant space where possible. Feels kinda greedy though
Does Devin will take over the jobs
No
Step 5, make it faster by using fast matrix exponentiation.
To solve dp you should solve dp 3 times.
..got it
At least the first couple times you learn about the concept, yes I believe so :)
So basically for loop is better than recursion 😊
In terms of performance, usually, but recursion lends itself to readability at times.
How is this dynamic programming? Looks like normal programming to me... 😅
Haha well it is still programming just a certain type of it
@@GregHogg sure sure, but I can't understand how it is anything different from normal programming where you divide the task into small sub tasks and solve those.
Recursion uses O(n) memory though
Indeed it does!
there's no need to inculcate such patterns, truth is in interview if you get DP is either you've done it and regurgitating it or you go blank
Is coding relevant in this AI era?
Yes
Memoization sounds like a baby tried to say memorisation 😂
the fastest method doesent use dp though
I wrote c#, i don't know if it can be done any other way than just using recursion with a limiting condition without making the code look like gibberish
me* watches how to solve dynamic programming problems
also me* messes up f-strings
Step 5: Binet's formula and rounding
What's that?
@@GregHoggthe analytical solution to the Fibonacci sequence
D&C, cht, lambda optimization, optimizations using fft entered the chat...
Or just us the formula in O(1)…
what formulat?
❤
5th solution:
Don’t use a program to solve a problem with an analytical solution. Takes the time complexity from O(n) to O(1).
sure, try doing all 4 of these steps in under 30 mins in an interview for a DP problem you have never seen before
Just remember: Dynamic Programming = Recursion + Memoizations
Dayem Greg
Personally don’t like this approach
I think learning straight the way to dp with an array is the correct way, this is how we’re thought in the University
The other are good ways to solve general problems, but not DP ones
It might be fun if I am employed by Netflix though.
Bro i can barely solve stacks medium. I am truly cooked.
You'll continue to improve, give it time 😄
I've heard "dynamic programming" so much over the years but had no idea it was just this, which I've been doing for years. I even recently wrote fib in Rust (arbitrarily chose it as a learning exercise) and immediately opted for bottom-up no-memory... because it makes the most sense. I remember first learning fib with recursion back in the day, but that's a pointless application.
Why is CDawgVA teaching coding😭?
Damn. I didn't understand a shit. Now I feel bad.
xD
60 seconds is a pretty short amount of time to learn 4 algorithms. This is a high level understanding video, it'll likely take more time than this to fully grasp :)
For a mathematician the first two solutions of Fibonacci are just weird.
Why solve the problem 4 times? Just write down the DP formulation and then write the code. Also step 4 is just for special cases. You don't know if the solution will depend on a constant number of previous values.
What do you mean, step 4 is just for special cases? When wouldn't it work?
@@TheStrandedAlliance Like I said, when the current value doesn't depend on a constant number of previous values. Or when you don't know which values to maintain in advance.
In the simple case of the fibonacci series, you only have to save exactly 2 values regardless of the current step, and you know which ones. In more complex problems you won't know in advance which values to save or how many. So you can't allocate O(1) memory for them and the only way is to maintain the whole table.
@@polycrystallinecandy Can't you just manage a dynamic list then? Also, in the recursive case, the values will just fill up the stack instead anyway, no? That would be pretty bad if you have a huge amount of values (-> stack overflow).
@@TheStrandedAlliance no, because you need to know ahead of time. By the time you get to the iteration where you know which values you should've saved, you've already lost them. You don't have to do recursive, you can do an iterative version (step 3), just save all the values in a table.
It's not steps, it's ways
Sometimes true. Agreed, you don't actually have to follow these steps if you know what you're doing. I'd argue it's a natural order to solving the problem, understanding it completely, and getting good practice in
🎁✅
Did you send me a gift haha
I spotted a trash, it is at the beginning, it resembles 🍎
What?
@@GregHogg I mean that logo in the center belonging to company engaged in slave labor in china.
cool
Anyone lost or just me
Good example but fibonacci could be solved with O(1) using math
precision issues will start to appear, also what if I want it modulo a large prime (like 10^9 + 7) and ask you to find the, for example, 748243191942148th Fibonacci number
impossible, logN runtime minimum
Show me the cpu that has a hardware integrated square root function. N64 doesn't count
@@nikolatesla3376no it isn't impossible. I did it on Leetcode. Unfortunately it depends on having an infinity accurate value for the golden ratio.
@@xxsuper99xx Square root of 5 can be precomputed and amortized, and it's not dependent on N
Had no clue what u just said
W
5th step cry
Too complex. Just learn the formal dp from Algorithm book.
I suggest "Introduction to algorithm III".
If there are overlapping subproblems and optimal substructure, then we can use dp.
Both top-down and bottom-up dp are tabulation.
(This vedio is not right.)
Tabulation means memorize the result to calculate everything in only 1 time.
Here are the steps to do dp problems:
1. Define the definition of your dp.
Ex. dp[i] means the minimum step to reach ith floor.
2. Write down the recursion.
Ex. dp[i] = dp[i-1]+dp[i-2] in Fibonacci.
3. Write down boundry conditions.
Ex. n = ?, then...
Hope this can help someone learning dp. : )
5th solution - i think you are lagging.
Hmm?
Imma fail
chatgpt ahh content
Ungrateful brat