Algorithms: Memoization and Dynamic Programming

Views 575 770
96% 6 752 242

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.

Science & Technology

Published on


Sep 27, 2016




Loading link...

Add to:

My playlist
Watch later
Comments 253
Crazy Chen
Crazy Chen 6 days ago
Is Dynamic Programming the same as recursion? The whole video is talking about solving problems using recursion. Not once did she explain what DP is.
Stanley Damasus
Stanley Damasus 11 days ago
I definitely agree with "use rows and columns vs x and y"
asdf 13 days ago
thankfully most programmers realize none of this garbage actually applies to their jobs or real life in general.
Brian Tep
Brian Tep 19 days ago
my memowee sux
Elma Paul
Elma Paul 21 day ago
Карьера программиста book in russian:)? For whom?
Dan T
Dan T 28 days ago
I really like how you copy/paste chunks of code without explanation and immediately just launch into an explanation. Not helpful at all.
Mollie tol
Mollie tol Month ago
0:32 how does fib(4) give 3!? I don't get this at all... part 1:fib(4-1) = 3, part 2: fib(4-2) = 2 so part1 + part2 => 3+2=5
Dragon Stone Creations
Is this a Breadth First Traversal ?
dot dot
dot dot 2 months ago
I guess i am still noob didn't get most of the things But I'll come back ,🙃
Marco Aurélio Nascimento
G-_ 2 months ago
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
Matthew Derbyshire
Matthew Derbyshire 2 months ago
surely, unless you're passing memo as a reference, the fib example won't work, as you're only passing down the array as it is on the branch above on that path down the tree?
Soup Spring
Soup Spring 3 months ago
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, {}))
Borja Cano
Borja Cano 3 months ago
I've undertood in 10 min something I did not in university. Good job :D
William 3 months ago
gayle is the one true god
Maksym Karunos
Maksym Karunos 3 months ago
Карьера программиста?
Shivraj Nag
Shivraj Nag 3 months ago
She seems like she could code every fucking problems that exists in the universe.......
Kuras FX
Kuras FX 3 months ago
Xavier J
Xavier J 4 months ago
This was easy to follow and understand. Thank you
Tesu Kim
Tesu Kim 4 months ago
Are the background books sponsors? '코딩인터뷰 완전분석' It doesn't seem like the Korean book is there for you to read.
Immovable Object Meets Unstoppable Force
I'm assuming this logic is aimed at finding only the most efficient paths to the end, because it surely didn't find all the paths.
Salomon Markovich
Salomon Markovich 4 months ago
is any of this useful for trading, anyone know?
Raj Yadav
Raj Yadav 5 months ago
I am her big fan in this programming world..
ctbram0627 5 months ago
Your memoized countPaths should have paths[row, col] = countPaths(grid, row+1, col, paths) + coutPaths(grid, row, col+1, paths); Also, I wrote this up in c# and I find it interesting that the non-memoized version always seems to be faster than the memoized version??? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 non-memoized paths = 72 Elapsed time non-memoization: 0.7299ms memoized paths = 72 Elapsed time memoization: 1.1516ms Where the memoized code is: public static int CountPathsMemo(int[,] grid, int row, int col, int[,] paths) { if (!ValidSquare(grid, row, col)) { return 0; } if (IsAtEnd(grid, row, col)) { return 1; } if (paths[row, col] == 0) { paths[row, col] = CountPathsMemo(grid, row + 1, col, paths) + CountPathsMemo(grid, row, col + 1, paths); } return paths[row, col]; }
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?!
Stephanie C
Stephanie C 6 months ago
8:54 You lost me. All I see is Minesweeper
alam md. sam sul
alam md. sam sul 7 months ago
im seeing nothing...too small..hand writing....!
JC Alpha
JC Alpha 7 months ago
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!
This video is awesome! But just two things in good ole code review: 1) The problem should be described as the "count the paths without going left or right" according to how the code was written. The more general problem of counting paths that don't loop back on themselves is similar but a bit different. 2) There is a bug in the recursive form of the algorithm presented around 5:48. There should be a check to make sure that (row+1 < len(grid) && col+1 < len(grid[row])). 3) Also, validSquare should really be validRectangle. The recursion has to be built for rectangles even if the inputs will always be squares. =)
Sundar B
Sundar B 7 months ago
Thank you, Gayle!
Paul Nguyen
Paul Nguyen 7 months ago
I think we can solve the last problem with O(n) space complexity. See below for the proposed solution. It's a little informal, but I can elaborate if someone needs, just reply to my comment asking for elaboration. Intuition: Using the "backwards" approach proposed at the end, we can throw away (or not keep in memory) any results that we aren't going to use again in future calculations as we propagate backwards. We only need to keep track of the values in the "lowest row", which means we only need O(n) values to track since a row has length n. Solution Proposal: We only need to track the values in the cells that will definitely have an impact in calculating the values of cells we haven't touched yet. Each cell only impacts the values of two other cells (let's call them dependent cells), i.e. the cells to the top and to the left. Once we have used a cell to calculate the values in the dependent cells, then we don't need to keep track of the value in the cell any more, only the dependent cells. If we start at the bottom rightmost cell and calculate the values of all cells going from right to left and row by row, we'll only ever need to keep track of approximately n values (since n is the size of a row).
Mohamed Naweeth
Mohamed Naweeth 8 months ago
hi mam, could u tell me the answer of this question Assume you are given n points in a D-dimensional space and an integer k. Describe the k-means ++ algorithm for clustering the points into k cluster
deputyVH 8 months ago
I didn't understand the iterative approach. What if you need to back track or side track? Then the number of paths are increased.
William Volen
William Volen 8 months ago
Lol. I thought they were all misspelling “memorization”
Bhavani Shankar
Bhavani Shankar 26 days ago
@ade putri u wut m8?
ade putri
ade putri 26 days ago
get ur degree dude
Dr Mohammad El-Nesr
No sir, *memoization* for computing is like *memorization* for humans. This expression was coined by Donald Michie in 1968 from a Latin word. I think they use this in computing because all variables in computer science are stored in Memory, so they are *memorized*, but for variables to be ready in an algorithm, they are *memoized*.
Programistyczna Samodzielność
What about loops? Why do you assume you can only go to the bottom or right?
Andrew White
Andrew White 9 months ago
В первом кадре на фоне книжка "Карьера программиста"))
Piotr Baranowski
Piotr Baranowski 9 months ago
Very high quality of the video. Great
Karim Sonbol
Karim Sonbol 9 months ago
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.
Thomas Yorkshire IV
Thomas Yorkshire IV 9 months ago
This code is completely wrong. First of all, memo[n] =fib(n-1) + fib(n--2) is obviously wrong because the function fib accepts two arguments, not one. So it should be memo[n] = fib(n-1, memo) + fib(n-2, memo). Second of all; else if (memo[n]) is also wrong because you are supposed to be checking if it has *not* been calculated yet so it should be: else if(!memo[n]).
Alexander Hernandez
Alexander Hernandez 10 months ago
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!!
Vipin Nair
Vipin Nair 10 months ago
Memoization :D
Hryhorii Liashenko
Hryhorii Liashenko 10 months ago
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); } }
Default 10 months ago
Why is it so easy for this to be explained here and not by my professor
Not John Cena
Not John Cena 11 months ago
Wouldn't the value at 7, 7 never be added as the recursion can't reach it?
DarthTofu2 10 months ago
And the two that is diagonally above the ending point. I noticed that, too. My instinct would have been to run an a* program to check if a given cell could be reached 1) from the start position and 2) could reach the end position. Just return 1 if it ever reaches the end, for each node having at most 2 connected nodes. Her way seems smarter
Younicorn Yolo
Younicorn Yolo 11 months ago
Why the recursive version of the second problem is O(2^(n^2))) ??
Vertigo 11 months ago
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
Shay Axelrod
Shay Axelrod Year ago
Sooo..... What is dynamic programming?
Andry Canel
Andry Canel 4 months ago
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.
Yaseen Mollik
Yaseen Mollik Year ago
Thanks a lot, Mam
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.
Jobert Cortes
Jobert Cortes Year ago
What programming language are you using for this algorithms?
Abi Ramez
Abi Ramez Year ago
Hi Gayle looking hot today 😉 , just came here to code 😂
Yash Aggarwal
Yash Aggarwal Year ago
sambdhiji video kyu
frankbraker Year ago
7:37 Can anyone tell me why is the simple approach O(2^(n^2)) please?
Greg Lockwood
Greg Lockwood Year ago
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.
Shivangi Singh
Loved the Maze example. Thank You!
Oke Uwechue
Oke Uwechue Year ago
How does this algorithm deal with walls that force the user to retrace their steps (in order to get out from a dead end)?
Greg Lockwood
Greg Lockwood Year ago
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.
Siddharth Chadha
QUESTION : Can anyone please explain me in detail why runtime at 7.46 is O(N^2)?
Ihor Mochurad
Ihor Mochurad Year ago
Big O of non-memoized solution: on each cell of the grid we can make 2 choices: go either down or to the right. Number of cells is N^2. Therefore, running time complexity is: O(2^(N^2)). If we have 4 cells (2*2 grid) = 2*2*2*2 = 16 = 2^(2^2) Big O of memoized solution: even though we visit each cell same number of times as before, we compute value of each cell only once and store the result in memo table. Number of computations is equal to number in cells in the grid = N^2.
Michael Brooks
Great job, Thanks for your sharing!!!
Bob The builder
I cant believe that approach to the number of paths problem. It's so simple yet not Intuitive. By the way you are a great teacher. I dont know if it's your voice or your great understanding of what your teaching or both but that was an amazingly explained video. Thank you I'm very grateful
Binsar Panjaitan
Brandon Salazar
I’m torn on this one. I suspect that it would be accepted in an interview. But it breaks if you ever have your blocked squares formatted in such a way that you’re forced to go left or up at least once before reaching the end
Paul Nguyen
Paul Nguyen 7 months ago
I think in that case we would use a different approach. She stated in her problem that the only paths we were counting were the ones that we could use to get from the start to the end using strictly down and right moves. The problem that you're speaking of is a different problem that has us additionally count paths that could use left or up moves, so a different solution is warranted. I think that if we proposed a solution to Problem X when you were asked Problem Y, then the interview might not go great for us. I bet she'd give a different solution if she was presented with a different problem.
Next videos