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.
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
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 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 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).
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.
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.
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.
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. : )
@@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
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?
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
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
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
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
@@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.
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 :)
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 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
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.
