Algorithms: Memoization and Dynamic Programming
Vložit
- čas přidán 26. 09. 2016
- 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.com/domains/tut... - Věda a technologie
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 CZcams 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.
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!!
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.
Loved the Maze example. Thank You!
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?
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.
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!
I definitely agree with "use rows and columns vs x and y"
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
I've undertood in 10 min something I did not in university. Good job :D
Same here
Thanks for the interesting video. Very concise and clear explanation of dynamic programming concept.
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!
Is it a coincidence that the frequency of fib(n) for the particular n at 1:59 follows the Fibonacci sequence?
Amazing, very good explanation, makes me understand the concept of memoization, thanks!
Best as always, Gayle Laakmann.
Thank you for making it so easy to understand !
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!
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.
This video is extremely well done!
You are such an amazing teacher!!
This is a concept that I wish a lot more developers would understand...
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
Thank you so much, you really enlightened my way!
Very well explained. Thanks.
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
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.
I like the "traditional" approach at 10 mins.
That is actually quite interesting and never thought about that
Thank you, Gayle!
Excellent video. Thanks.
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.
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.
Awesome video in illustrating difficult concepts
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
Why the recursive version of the second problem is O(2^(n^2))) ??
Great explanation. Thank you!
Reading her book now. Pretty informative.
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.
For the last example at 7:50, can you count and fill the matrix from the top left to the bottom right?
is runtime Big O of N squared - as you describe it? or is it Big O of 2 to the Power of N Squared - as displayed on the screen? As I understand its the former.
Thanks! Very clear explanation.
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!
how can you even reach 7, 5th box top left if the above box is blocked? the search should not calculate that.. isnt it?
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?
This is an excellent resource.
your concepts are banging stars!!!!! (y)
Good explanation of memoization !!!
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 .
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.
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!
When 5000 people beg at Google's doorstep for the same position, this is the inevitable result. The winner is the person who maximizes their ability to game heavily standardized interview processes. All this lady did was level the playing field and make heaps of money off it.
Amazing 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)).
For purposes of conceptual symmetry when partitioning space I too use y as column and x as row. Which order x and y appear in as an index for a matrix is arbitrary (column or row major order). Preserving the idea of x as the horizon is orienting for me. Are you using some kind of projection logic to resolve the inconsistency or do you just accept the x as column without question as a best practice? Also, this is a great video. Thank you.
Best Teacher, thanks
space complexity of recursive solution for fibonacci series very well explained.
Great job, Thanks for your sharing!!!
Can the memo array be initialised with 0 and 1 and then the 2 ifs be removed?
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.
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.
Hello, What is the software used to draw ?
what is the software you use for drawing?
very useful video. Thanks
What about loops? Why do you assume you can only go to the bottom or right?
This was easy to follow and understand. Thank you
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.
is any of this useful for trading, anyone know?
Which software are they using for writing the text in the video?
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
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.
This was great!
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?
Best videos eveeerrr!! Matrix problems I just use i and j.
What do the words associative arrays , lookup table,cache hit/miss ratio have in common with memoization?
Is this a Breadth First Traversal ?
For the path problem, dp solution's space complexity is actually 2(n^2) but it is admissible as (n^2)
And we don't fully get rid of call stack since the method is still recursive. But since we store the values, our call stack grows up to a certain degree that is negligible.
Does that what she mean at the end of the video ?
Might be misunderstanding your comment but I think it’s because she’s talking big O so the 2 * n^2 is reduced to n^2?
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)
I have a bachelors in Computer Science and this still has been incredibly helpful in keeping my fundamentals sharp!
I didn't understand the iterative approach. What if you need to back track or side track? Then the number of paths are increased.
Thanks for this video.
Why is the space complexity for the non-memorised solution is O(n)? I can't figure it out, can someone explain?
The space complexity is the maximum space a program takes at a particular time, as at a time instant "t" the stack has only n functions to perform and as at new time instant "t+1" one function is executed so removed from the stack and new function is added so net n functions only remain at a particular instant hence it is O(n)
This is great. :)
How does that code handle the case where it has zero paths to the end? Would that not cause compilation or run-time error?
It has a validation function that checks whether or not the path down or right are possible paths and returns 0 instead of 1. The other squares are pretty much made up by adding the values of the squares after its right and below it in the call stack till you hit the base case (you reaching the end which returns 1) so it would just be a square with a value of 0 and add 0 to any square above it or to its left, hence why the square above it equals 1 rather than 2.
Wouldn't this break if there were enough blocks requiring the path to go up or left?
Would have been nice to see the explanation of adding in the memo array
What Kind of Illustration program is she using for the presentation?
I want to know this as well, doing a quick google search didnt come up with much
Paint
when I do return countPaths(grid, row + 1, col) + countPaths(grid, row, col + 1); I get index out of bound how / why do you not account for this? what am I missing? Thanks!
Maybe that was supposed to be taken care in the validSquare function.
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.
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, {}))
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 7:30 why do we have to check if paths [row][col] == 0 ?
To check whether or not there has been a stored calculated path on that specific row and column. This makes the program not use unnecessary steps to calculate a previously calculated path. Thus, it lowers the run-time of the program.
Understood the memorization approach in case of matrices.
How does this algorithm deal with walls that force the user to retrace their steps (in order to get out from a dead end)?
It doesn't. In order to retrace your steps, you would need to either travel left, or up. Which was not allowed according to the problem definition.
Which software this presentation was created with?
Are the background books sponsors? '코딩인터뷰 완전분석' It doesn't seem like the Korean book is there for you to read.
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
what is the fourth parameter int[][] paths mean at 7:30 ?
Hello, that fourth parameter is an integers matrix that holds the number of paths each cell has towards the end and we check if paths [row][col] == 0 because I assume they initialized it as a matrix full of zeroes, so if it has a 0, then it hasn't been computed yet and you need to memorize it.
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
Is this code correct? I do not happen to know what language or pseudo language is intended. Written in video .... if (memo[n]). Should that be corrected to ... if (memo[n] < 0) ? .. It seems you would update the value if it does not have a value > 0. The default value is not specified. Should the video be annotated?
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.