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!
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.
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.
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
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!
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.
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
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!!
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.
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).
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, {}))
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?
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?
@@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
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
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?
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 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
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)).
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 .
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.
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
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.
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
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.
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.
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.
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 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. =)
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?!
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
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]; } }
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)
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.
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.
awesome video, easy to follow. the recursive examples seemed a bit unnecessary, but it does help put how efficient dynamic programming is into perspective
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
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.
You need to recalculate after every fib() call. It's a recursive function. Also, fib(4) means that 4th fibonacci number, and that's 3. 0 1 1 2 3(It's start from 0 - fib(0) = 0)
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
Sorry, but if you are writing in Java, why don't you use class property instead of passing the same additional parameter for every function you use. It's a proxy pattern. Also, your painting reminded me with the old days of 'minesweeper game on windows 2000', thanks *_*
I don't understand why you shouldn't use x and y coordinates. I like them. And how is x the column like you said? X is always the row and y is always the column
If you are careful to keep x to always mean row number, and y to always mean column number, then using x and y is equivalent to using row and column. The problem comes because "x" normally means "how many units across", and "y" means "how many units up or down". But for a grid, the unit that increases going across is the column number, and the unit that increases going down is the row number. So the problem comes from using a confusing choice of variable name, where the universal understood meaning of "x" and "y" do not apply. That is not clear, readable code. It might be to you, but working professionally means it has to be readable to others. In fact, the vast majority of others.
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 ?
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.
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
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.
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
![Blox Fruits Dragon Rework Update [Full Stream]](http://i.ytimg.com/vi/EqDAp8udhm0/mqdefault.jpg)
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 RUclips channel. Glad I did!
How does the program stop at 0 , why does it not go to negative values
Good!!
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.
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!
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!
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.
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.
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
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!
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
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.
I have a bachelors in Computer Science and this still has been incredibly helpful in keeping my fundamentals sharp!
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!!
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
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 definitely agree with "use rows and columns vs x and y"
I like the "traditional" approach at 10 mins.
That is actually quite interesting and never thought about that
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 a concept that I wish a lot more developers would understand...
Best as always, Gayle Laakmann.
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, {}))
Is it a coincidence that the frequency of fib(n) for the particular n at 1:59 follows the Fibonacci sequence?
Thanks for the interesting video. Very concise and clear explanation of dynamic programming concept.
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.
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!
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
Amazing, very good explanation, makes me understand the concept of memoization, thanks!
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 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
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
6:08 Code example countPaths(grid, row+1) + countPaths(grid, row, col+1)
Loved the Maze example. Thank You!
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)).
You are such an amazing teacher!!
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 .
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.
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.
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
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.
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.
Awesome video in illustrating difficult concepts
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.
space complexity of recursive solution for fibonacci series very well explained.
This is an excellent resource.
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.
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.
Which software this presentation was created with?
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
Why the recursive version of the second problem is O(2^(n^2))) ??
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 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. =)
This video is extremely well done!
Thank you for making it so easy to understand !
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?!
Using the explicit formula for fibonacci numbers, you can implement it in O(log n) time.
How?
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.
6:40 that hit me , I was on a coding challenge and couldn't finished on time cause I put i and j wrong
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)
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?
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.
Forgotten to write:
if (row > max || col > max) return 0;
otherwise row and col keep increasing and will buffer overflow
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.
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.
Best videos eveeerrr!! Matrix problems I just use i and j.
Great explanation. Thank you!
Thank you so much, you really enlightened my way!
awesome video, easy to follow. the recursive examples seemed a bit unnecessary, but it does help put how efficient dynamic programming is into perspective
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
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.
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
You need to recalculate after every fib() call. It's a recursive function. Also, fib(4) means that 4th fibonacci number, and that's 3. 0 1 1 2 3(It's start from 0 - fib(0) = 0)
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
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
I am her big fan in this programming world..
Amazing explanation!
your concepts are banging stars!!!!! (y)
Good explanation of memoization !!!
Sorry, but if you are writing in Java, why don't you use class property instead of passing the same additional parameter for every function you use. It's a proxy pattern.
Also, your painting reminded me with the old days of 'minesweeper game on windows 2000', thanks *_*
Because she isn't teaching Java. She is teaching algorithms. It just so happens to be that most people are familiar with Java syntax.
I didn't understand the iterative approach. What if you need to back track or side track? Then the number of paths are increased.
What do the words associative arrays , lookup table,cache hit/miss ratio have in common with memoization?
gayle is the one true god
You speak perfectly well and this is an excellent video. Thank you.
For the last example at 7:50, can you count and fill the matrix from the top left to the bottom right?
I don't understand why you shouldn't use x and y coordinates. I like them. And how is x the column like you said? X is always the row and y is always the column
If you are careful to keep x to always mean row number, and y to always mean column number, then using x and y is equivalent to using row and column. The problem comes because "x" normally means "how many units across", and "y" means "how many units up or down". But for a grid, the unit that increases going across is the column number, and the unit that increases going down is the row number.
So the problem comes from using a confusing choice of variable name, where the universal understood meaning of "x" and "y" do not apply. That is not clear, readable code. It might be to you, but working professionally means it has to be readable to others. In fact, the vast majority of others.
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?
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.
Thank you, Gayle!
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
What about loops? Why do you assume you can only go to the bottom or right?
Are the background books sponsors? '코딩인터뷰 완전분석' It doesn't seem like the Korean book is there for you to read.
At 10:20, How is the run time for counting paths using dynamic programming O(n^2) ? We just visit each cell once. Shouldn't it be O(n) ?
G lakshmeepathi how many cells are in an nxn grid? n^2 cells.
Would have been nice to see the explanation of adding in the memo array
Wouldn't this break if there were enough blocks requiring the path to go up or left?
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.
Wouldn't the value at 7, 7 never be added as the recursion can't reach it?
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
Is this an official HackerRank channel?
2:37 is not even fib(1) already computed?
Thanks for this video.
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.
What is dynamic programming?