Algorithms: Memoization and Dynamic Programming
Вставка
- Опубліковано 25 сер 2024
- Learn the basics of memoization and dynamic programming. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.
www.hackerrank....
0:00 Gayle Laakmann McDowell
0:14 Example Fibonacci's
4:26 Example Maze
Dynamic programming:
breaking-down into subroutines;
store/memorize subroutines;
reuse subroutine results.
thank you!
top one was most important thx
0:00 Gayle Laakmann McDowell 💀
Bought the books years ago. Just stumbled onto this UA-cam channel. Glad I did!
How does the program stop at 0 , why does it not go to negative values
Good!!
This is an amazing video. I request to post more videos on dynamic programming (memory+recursion). This video was very helpful. keep up the good work.
Dynamic programming problems are the hardest to grasp for me, but this was really beneficial, especially for problems involving DFS
Congrats on your job at Google ;)
Congrats on your job at Google!
This is so good! She concises my 2.5 hrs lecture into 11 mins.
i can EXACTLY agree with this. 3 hour lecture for MSc CS class in 11 minutes.
at 04:00 for mem version
Shouldn't be like below?
else if (!memo[n]) memo[n] = fib(n-1, memo) + fib(n-2, memo);
Exactly what I was thinking.
I am 100% agree with you
I agree Dmitry. I'm checking for negative values instead in Swift.
static func fib(n:Int, memo:inout [Int])->Int{
if n
yep, it's a bug =)
Would if(!memo[n]) mean If memo[n] hasn't been created yet?
I've undertood in 10 min something I did not in university. Good job :D
Same here
Thank you so much this is a magnificent explanation. Super clear I was able to write the code and ut works perfectly. I don't mind the typos it is clear to understand despite those. Thanks!!
You say “the reason is THAT...” instead of the more common and painful “the reason is BECAUSE...” 😍😍😍
Thank you!!!!
That alone makes this video awesome!
Thank you very much for the explanation. I was solving the unique paths problem couple of days ago and I was getting exponential time while submitting the answer. Never realized that we could memorize the repetition of work.
Thanks to this lady, the entire interview process is in the gutter! Congratulations on single-handedly destroying the creative interviewing process and turning it into a graded exam!
I definitely agree with "use rows and columns vs x and y"
Though it's a really helpful tutorial of DP (Thanks to Gayle), I think the memoization solution of maze problem misses a parameter in the recursive call. The correct code should be:
int countPaths(boolean[][] grid, int row, int col, int[][] paths) {
if (!isValidSquare(grid, row, col)) return 0;
if (isAtEnd(grid, row, col)) return 1;
if (paths[row][col] == 0) {
paths[row][col] = countPaths(grid, row + 1, col, paths) + countPaths(grid, row, col + 1, paths);
}
return paths[row][col];
}
In this case, the function will be able to check the paths 2-D array to retrieve the result already calculated.
Looking forward to your feedback!
1:44 Notice how the frequency of each item other than 0 forms the Fibonacci sequence.
fib(6): 1 occurrence
fib(5): 1 occurrence
fib(4): 2 occurrences
fib(3): 3 occurences
fib(2): 5 occurences
fib(1): 8 occurences
holy shit bro :0
Thanks for the interesting video. Very concise and clear explanation of dynamic programming concept.
Notice that her underlined if statement (at 7:21) can still unnecessarily call the countPaths function multiple times because the zero value it is checking for could have come from either the INITIAL zero value (originally stored in the paths matrix), or a CALCULATED zero value returned from countPaths. Simple initializing all the values in the paths matrix to -1 at the beginning and then checking for a -1 (instead of zero) in that same if statement will fix that.
True dat
@@isaacdouglas1119 Why are there so many damn flaws in their code lmao how am i suppose to learn.
I like the "traditional" approach at 10 mins.
That is actually quite interesting and never thought about that
Amazing, very good explanation, makes me understand the concept of memoization, thanks!
I have a bachelors in Computer Science and this still has been incredibly helpful in keeping my fundamentals sharp!
Loved the Maze example. Thank You!
8:26 Actually that cell is unreachable from the green guys current position, because he can't go left or up.
Same with the 5 cells (7, 4, 1, 1,1) in the bottom left corner.
But I assume you mean that each number represents all available paths IF the guy would have stood in that specific cell?
Yes those cells are unreachable, but it doesn't affect the correctness of the algorithm. The cell at 8:26 is prevented from summing into the final no. of paths because of the blocks to the top and left. A cell which is unreachable to the green guy is always a cell with blocks to the top and left. So by this logic you can convince yourself the algorithm won't sum up paths through unreachable cells.
Best as always, Gayle Laakmann.
Is it a coincidence that the frequency of fib(n) for the particular n at 1:59 follows the Fibonacci sequence?
else if (memo[n])
Isnt this condition saying if array memo of index n is filled? but shouldn't it be !memo[n] cause we are trying to fill up the array?
Alot of the time man it's just situational and can vary from project to project
@@FreakinKatGaming what kind of bullshit answer is this. Plain and simple this code will return null if the value haven't been computed. @Foolish Music you are correct when it comes to the code that they showed.
@@basicnamenothingtoseehere 🤣 wow you a took that seriously. Bless your little heart . Omg you made my day, ain't you just the cutest little Dickens!!!! Man my day was NULL until I read this man variables are awesome. 😅😋 Nahh but why not apt moo - around
@@FreakinKatGaming shut the fuck up brother
@@daruiraikage I'm typing not speaking, if ya gotta problem block me. That simple. Otherwise make me!
At 07:22, in your DP code, you are calling the countPaths method without the fourth parameter, which is paths.
Excellent video. Thanks.
Both the DP codes are like that. There should be a memory parameter in the function call isn't it...?
@@RavinduKumarasiri Yes!! it's just a typo
This is a concept that I wish a lot more developers would understand...
06:50 To be clear, don't use Cartesian x and y when dealing with matrices.
using pairs of (x,y) will decrease the key press when implementing the algorithm rather using those matrix representations just kidding.
This was honestly one of the most helpful tips I have ever received. When I started out programming, trying to use x and y, I wasted hours working around grid coordinates in my head.
so use j,k as indicies? jk.
or just use x & y and think in Cartesian
its not actually that hard to convert beetween rows&columns to Cartesian x&y and the other way
and by making it cartesian you can do x,y instead of y,x because in cartesian x is usually defined before y
or to go trought use r & c instead of row & col
Label things whatever is meaningful to the situation.
Thank you so much Gayle!
Upvoting this as the only positive and thankful answer in the entire comments thread :P
shamassive thanks a lot! It was helpful to me.
Great explanation! In the last example, the space complexity can be reduced to O(n) because we only need two rows or two columns of values if we sweep the matrix row by row.
If you count the presence of the original grid, the space complexity with be O(n^2) regardless. If you don't count the grid, you can define the grid in a way to modify it in place and the space would be O(1).
Actually even in this implementation we can make constant space. Just keep only 2x2 subgrid at each step.
This is an excellent resource.
You are such an amazing teacher!!
Point to be noted- We will never reach sqaures with 7,4,1,1 in first column, as we can only go right but not left.
So I wasn’t sure about that. The way she coded it up, you would never hit the square with 7 paths, but that is a valid path which leads me to believe that the algorithm was slightly incomplete, no? I mean, that _should_ be a valid path, but if we have checking left and right in the same recursion then we would never leave the loop. How would one handle that scenario?
@@JeffPohlmeyer Yeah, there are two ifs missing before the recursive calls. A recursive call can only be done if the adjacent cell is obstacle free.
at 2:14 the memoization code for Fibonacci is incorrect. This would be the fix (pink line of code)-
else if (!memo[n]) {
memo[n] = fib(n-1, memo) + fib(n-2, memo);
}
In Python:
def fib(n, memo):
if n==0:
memo[n] = 0
return 0
elif n==1:
memo[n] = 1
return 1
elif not n in memo:
print(n)
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
print( fib(5, {}))
space complexity of recursive solution for fibonacci series very well explained.
Awesome video in illustrating difficult concepts
I once stumbled onto the misconseption you mentioned when using y as rows and x as columns and now I just figured it out why it happened then 😅. When we use the grid representation it would be good to indicate that arrows pointing the directions mean that its the way where row numbers are increasing and not neccessarily the way that rows are aligned I’m kind of dumb but if anyone else had this problem that might be the answer
Best videos eveeerrr!! Matrix problems I just use i and j.
The idea of the second one is correct, but I think it is more obvious if we start from the top left.
the number in each position stands for how many paths can lead the little green guy to there.
First fill matrix[0][i] (i.e. row0) and matrix[j][0] (i.e. col0) with 1 if there is no barricade, if there is, fill them with 0;
since the little green guy can only move to the right or down at each step, so the value of the inner matrix, should be the sum of the matrix[i-1][j] + matrix[i][j-1]
1 1 1 1 1 1 1 1
1 2 X 1 2 3 X 1
1 3 3 4 X 3 3 4
X 3 X 4 4 X 3 7
0 3 X 4 8 8 11 18
0 3 3 X X 8 X 18
0 X 3 3 3 X 0 18
0 0 3 6 9 9 9 27
This helped alot thank you!
That's some good insight!! Thank you :)
Nice algorithm, I didn't hear about the requirement that could only move to the right or down so now it makes sense to me. Without that requirement, how do you think the algorithm would be?
AA
6:40 that hit me , I was on a coding challenge and couldn't finished on time cause I put i and j wrong
Thank you for making it so easy to understand !
6:08 Code example countPaths(grid, row+1) + countPaths(grid, row, col+1)
This video is extremely well done!
Thanks! Very clear explanation.
How'd she calculate the "(simple) Recursive" runtime of O(2^{n^2})? (7:25) I think because there are n^2 possible cells (assuming the problem is run on an n by n grid), and at each cell there are a maximum of two possible moves that would add to a path: go down, or go right. By the basic principle of counting (generalized), there are 2^{n^2} possible outcomes/paths to check for existence, thus the running time is O(2^{n^2}).
Nah it should be O(2^n) because we’re using Manhattan distance here. So every path from start to end is n grids, and at every grid you choose to go right or down, hence 2^n
@@baiyuli97 I got the same answer. I drew out the call tree for N=4, and there are only 7 levels. This means there are 2N - 1 levels, and each node has 2 child nodes. So, it's O(2^n) because the constants go away. Another way to think about it is to draw out the grid and count the steps. Regardless of the order in which you traverse the tree, ultimately you will need to move N - 1 to the right and N - 1 down. If you count the start node as a step, that's 2N - 1. So, any given path will be 2N - 1 deep. I might be wrong, but I can't figure out how she got O(2^(n^2)).
Great explanation. Thank you!
Why the recursive version of the second problem is O(2^(n^2))) ??
Thanks for this video.
Reading her book now. Pretty informative.
Recursion approach with just down/right direction wont' work, you have to try all directions for some cases. But the second DP one brilliant
Had the same thought process. Happy that I'm not alone.
I like the methodology for figuring out a solution, but your path traversal breaks down if you're bottlenecked by a zigzag pattern of unavailable spaces where the only way to get to the end is to go right, down, and then left before you can resume going down and to the right
Good explanation of memoization !!!
n=int(input("how many do you want?"))
x,y = 1,1
for i in range(1, n):
print(x)
x,y = y, x+y
Thank you so much, you really enlightened my way!
your concepts are banging stars!!!!! (y)
In the dynamic programming approach, I think we can have only O(n) space complexity, since we only need to store the values in the current row in the grid and the one below it.
Amazing explanation!
If you can only move right and down, then the path on the left most starting at 7 [4][0] to [7][0] downward including that 1 [7][1] is impossible. Same with the 2 [6][6] right at the end. You just cannot get to those squares.
Yes, also having a matrix that looks like this (where 0 means empty space, X means blocked, S start and E end) would be impossible, when there is clearly a path:
S X 0 0 0
0 X 0 X 0
0 0 0 X E
Yes but what if you were spawned that those squares ? The number suggests how many paths are there if you start from there.
Which software this presentation was created with?
Thank you, Gayle!
How can we call a 2 parameter function with one? Shouldnt the code be more like
else if (memo[n]) return memo[n]; ? Then another else for putting the calculation in the memo?
that code is not accurate, the concept is right, but the implementation is not accurate in my opinion. You could refer to www.geeksforgeeks.org/program-for-nth-fibonacci-number/ for the correct implementation
Yeah this stumped me for a minute until I realized it's not correct
Actually she was right, it just a bit difficult to understand without seeing the full implementation. You guys can follow her full implementation here: github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2008.%20Recursion%20and%20Dynamic%20Programming/Q8_01_Triple_Step/QuestionB.java
public static int countWays(int n) {
int[] map = new int[n + 1];
Arrays.fill(map, -1);
return countWays(n, map);
}
public static int countWays(int n, int[] memo) {
if (n < 0) {
return 0;
} else if (n == 0) {
return 1;
} else if (memo[n] > -1) {
return memo[n];
} else {
memo[n] = countWays(n - 1, memo) + countWays(n - 2, memo) + countWays(n - 3, memo);
return memo[n];
}
}
@Kutay Kalkan yes , it should return memo[n] if memo[n] is positive.
or it can be the negation in her case . if it was missed.
What is dynamic programming?
I am her big fan in this programming world..
Excellent video. Thanks.
Very well explained. Thanks.
Awesome tutorials but I think the example for DP might be improved a bit.
From the given example of dynamic programming for the Fibonacci numbers is not obvious what should be the memo[] length. I think the more simpler for understanding example is to use a HashMap.
static HashMap memo = new HashMap();
static int fibonachiDp(int n) {
if (n == 1 || n == 2) {
return 1;
}
if (memo.containsKey(n)) {
return memo.get(n);
} else {
memo.put(n, fibonachiDp(n - 1) + fibonachiDp(n - 2));
return memo.get(n);
}
}
Memo length is n. Your code is elegant but unless you can guarantee that your hash table operations work in constant time, her implementation is faster. Note: hash can be guaranteed to be work on constant time with load factor and uniform distribution of keys but the constant is usually large.
Great job, Thanks for your sharing!!!
In the Fibonacci example why do you do “if else memo[n]” rather than “if else !(memo[n])”? Aren’t you checking if there is a value and if there isn’t (ie it is NULL) then calculate it?
Best Teacher, thanks
at 10:24...
the first column to the left after the pink square all have 0 paths; because you can only go to the right and down only so you can't go left .
Using the explicit formula for fibonacci numbers, you can implement it in O(log n) time.
How?
very useful video. Thanks
7:37 Can anyone tell me why is the simple approach O(2^(n^2)) please?
That problem is fairly similar to the fibonacci problem, and you can model it in the same way as a binary tree. It's binary because we call the function recursively twice in each iteration. Since you have to traverse the entire tree, then we have O(2^(time complexity for one cell)). The algorithm to compute the number of paths from any cell to the destination for the simple, brute-force algorithm is O(n^2), since it has to traverse the whole grid and sum up paths as it goes. Remember, this is with no memoization, so it does the same work over and over again. Therefore, the final time complexity is O(2^(n^2)). It's a good example of how much better the memoized version is. It only has to traverse the grid once. The rest is just constant time lookups.
First case, with recursion, we run two parallel paths to find the distance. Move Right, Move Down (total 2 counts) times all the boxes. Hence two times N^2.
In second approach, If there is a 10x10 maze, we have to run the loop 100 times to fill the boxes in the matrix and find the answer. Hence it is just N^2.
If we can memoize, which is to store the paths in a map, then it will save some time cost and bring it down to N^2 for the recursion approach itself.
I dunno, for the case of non-memonization: I believe it is 2^(2n) calls to the function. If you draw the recursion tree, at every level the number of nodes doubles.
Now we need to find the depth of the tree. When we go down the tree either the x coordinate or y coordinate increases. Both these numbers can only increase up to n, so in 2n calls we will be at the destination.
2n depth means number of calls is \sum_{i=1 to 2n} 2^i = 2^(2n)
Forgotten to write:
if (row > max || col > max) return 0;
otherwise row and col keep increasing and will buffer overflow
You speak perfectly well and this is an excellent video. Thank you.
8:18 Why just one path? There are three blank cells in the second-to-last row which create more paths.
I think the rule is: can't go up or left. I think you didn't mention that rule.
Aslo, i think you didn't mention why diags are disallowed. I assume the rule is you can only increment row or column for a step, not both.
Mam please produce more videos
What is the purpose of your if test for memo[n]. You left out the == 0 .Don’t you only want to compute it if it’s not cached and return the one you have cached.
Подборка книг на фоне впечатляет ;)
"Карьера программиста" - наши и там корни пустили :)
Gayle - это Галя чтоли?)
any good books that is leading one into problemsolving and problemsolving techniques? Cheers
Her book obviously, Cracking the Coding Interview
I'm not sure if it would suit a complete beginner in algorithms.
Try Grokking Algorithms
Think like a programmer by V. Anton Spraul
Grt online teacher
Hi, I did a small program to test what she said. Here it is:
class Fib{
public static void main(String args[]){
long start = System.nanoTime();
System.out.println(fib(6));
long end = System.nanoTime();
System.out.println(end-start);
start = System.nanoTime();
System.out.println(fib1(6));
end = System.nanoTime();
System.out.println(end-start);
}
public static int fib(int n){
return fib(n, new int[n+1]);
}
public static int fib(int n, int[] mem){
if(n==0)
return 0;
else if(n==1)
return 1;
else if (mem[n]==0)
mem[n]=fib(n-1) + fib(n-2);
return mem[n];
}
public static int fib1(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
else return fib1(n-1) + fib1(n-2);
}
}
I get this result:
// Recursive Solution
8
295978
// Recursive Solution with memoization
8
37240
The memoization solution is almost 8 times faster.
*Almost 8 times faster at your given n. As n increases the O(2^n) function gets worse and worse.
gayle is the one true god
Sooo..... What is dynamic programming?
The whole concept is dynamic programming. Storing the result of a sub problem to a problem and reusing that answer to solve other sub problems . A problem needs to have overlapping sub problems to be a dynamic programming problem. Memozation is just a way to do a DP problem. There is also tabuoation.
What do the words associative arrays , lookup table,cache hit/miss ratio have in common with memoization?
I think you could specify more clearly that you are only moving to the right or down at the outset with that matrix problem, as there are several situations when you could move up and then down and still get to the bottom, for example with that "zero" path square.
she explains it pretty clearly at 4:16
This was great!
at 8:33 that cell should have zero paths... since the block above and to the left are both blocked off, there is no way for the little man to ever stand on that square?!
Great video, can I ask what tools did you use for the graphics and drawings ?
Isn't Can i ask technically a glitch, when you have already asked what you wanted to ask when asking for the permission to ask.
@@mayankgupta2543 Only if you read everything literally, which is misunderstanding the language.
So what was the last part going from bottom-up about? Is it just running the example or showing us a different way to do code it?
This is great. :)
This was easy to follow and understand. Thank you
awesome video, easy to follow. the recursive examples seemed a bit unnecessary, but it does help put how efficient dynamic programming is into perspective
0:38. I usually call it 'Fibo Six'.
Would have been nice to see the explanation of adding in the memo array
I always get confused on logic that increments multiple parameters in counter functions in such cases as she just showed at 06:00 she returns the sum of CountPaths(grid, row+1, col) and countPaths(grid, row, col+1); My bad habit of thinking is I have the tendency is to want to write return CountPaths(grid, row+1, col+1). Even after learning thats not correct.. for some damn reason my mind keeps thinking thats how it should be done. Such a bad habit I have. As if code was that simple.. hehe
7:56 how did you figure out what the recursion approach does? Like i can't even wrap my head around the recursive tree especially at the end .. please reply
Very high quality of the video. Great
Understood the memorization approach in case of matrices.
For the last example at 7:50, can you count and fill the matrix from the top left to the bottom right?
Could someone explain the condition of paths[row][col] == 0 in the memoization solution?
With a memoization solution, the goal is to eliminate the need to repeat calculations that have already been calculated. Initially, the solution could be broken down from path(start, end) = path(A, end) + path (B, end). These separate ones can be broken down (recursively) even further: path(A, end) = path(D, end) + path (C, end) and path(B, end) = path(C, end) + path (E, end).
See here, path(C, end) is already repeated. So passing in an additional array, in this case paths[][] can store the values that have been calculated.
The condition is thus necessary to check before further calculating. If paths[row][col] already has a value, then just return the value. If paths[row][col] is 0, then then value has not been calculated yet, so calculate it.