Algorithms: Memoization and Dynamic Programming

[@zingg7203]

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.

[@annaphuong3260]

thank you!

[@II_xD_II]

top one was most important thx

[@recursion.]

0:00 Gayle Laakmann McDowell 💀

[@SteversIO]

Bought the books years ago. Just stumbled onto this KZbin channel. Glad I did!

[@tejasp7700]

How does the program stop at 0 , why does it not go to negative values

[@videovideoguy]

Good!!

[@jialiliang3606]

This is so good! She concises my 2.5 hrs lecture into 11 mins.

[@trollface1994]

i can EXACTLY agree with this. 3 hour lecture for MSc CS class in 11 minutes.

[@dmitrys256]

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);

[@raulnunez7580]

Exactly what I was thinking.

[@alexqiu3782]

I am 100% agree with you

[@MauriceMickens]

I agree Dmitry. I'm checking for negative values instead in Swift. static func fib(n:Int, memo:inout [Int])->Int{ if n

[@xalspaero]

yep, it's a bug =)

[@TheSportstar77]

Would if(!memo[n]) mean If memo[n] hasn't been created yet?

[@ujjvalsharma5055]

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.

[@ififif31]

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.

[@isaacdouglas1119]

True dat

[@davidyang5131]

@@isaacdouglas1119 Why are there so many damn flaws in their code lmao how am i suppose to learn.

[@kidou123456]

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!

[@Seborgium26]

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

[@iamnotahuman2172]

holy shit bro :0

[@sunnilabeouf]

Dynamic programming problems are the hardest to grasp for me, but this was really beneficial, especially for problems involving DFS

[@omarfares1389]

Congrats on your job at Google ;)

[@dbzkidkev2]

Congrats on your job at Google!

[@ScottGrodberg1]

06:50 To be clear, don't use Cartesian x and y when dealing with matrices.

[@pchandu1995]

using pairs of (x,y) will decrease the key press when implementing the algorithm rather using those matrix representations just kidding.

[@tiny_paul]

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.

[@brokenjava11]

so use j,k as indicies? jk.

[@Anohaxer]

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

[@BlackJar72]

Label things whatever is meaningful to the situation.

[@ThousifSMd]

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.

[@Bodyja]

I've undertood in 10 min something I did not in university. Good job :D

[@mir6326]

Same here

[@mehmetdemirel6809]

At 07:22, in your DP code, you are calling the countPaths method without the fourth parameter, which is paths.

[@michaelstueben2880]

Excellent video. Thanks.

[@RavinduKumarasiri]

Both the DP codes are like that. There should be a memory parameter in the function call isn't it...?

[@keerthi71815]

@@RavinduKumarasiri Yes!! it's just a typo

[@sebbes333]

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?

[@elliotheisler1437]

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.

[@b4singularity]

I definitely agree with "use rows and columns vs x and y"

[@SS-iz9vo]

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, {}))

[@jc_alpha]

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!

[@uzdik.student]

Which software this presentation was created with?

[@axandermorales]

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!!

[@lepakshi123]

Best as always, Gayle Laakmann.

[@mingyan8081]

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

[@ultimatesin3544]

This helped alot thank you!

[@keerthi71815]

That's some good insight!! Thank you :)

[@xhenryx14]

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?

[@fieworjohn5697]

AA

[@RegularTetragon]

Is it a coincidence that the frequency of fib(n) for the particular n at 1:59 follows the Fibonacci sequence?

[@stanst2755]

Thanks for the interesting video. Very concise and clear explanation of dynamic programming concept.

[@johnc4624]

I like the "traditional" approach at 10 mins. That is actually quite interesting and never thought about that

[@foolishmusic9430]

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]

Alot of the time man it's just situational and can vary from project to project

[@basicnamenothingtoseehere]

@@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.

[@FreakinKatGaming]

@@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

[@daruiraikage]

@@FreakinKatGaming shut the fuck up brother

[@FreakinKatGaming]

@@daruiraikage I'm typing not speaking, if ya gotta problem block me. That simple. Otherwise make me!

[@Irwansyah-kq8lf]

Amazing, very good explanation, makes me understand the concept of memoization, thanks!

[@ShivangiSingh-wc3gk]

Loved the Maze example. Thank You!

[@xinyucao5550]

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.

[@Grassmpl]

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).

[@Grassmpl]

Actually even in this implementation we can make constant space. Just keep only 2x2 subgrid at each step.

[@carolinaalbamaruganrubio2446]

You are such an amazing teacher!!

[@riyadshauk2432]

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}).

[@baiyuli97]

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

[@summerzeelee]

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

[@khalifacastaway6356]

Awesome video in illustrating difficult concepts

[@julienbongars4287]

This is a concept that I wish a lot more developers would understand...

[@jaimeduncan6167]

This is an excellent resource.

[@luis-azanza]

Thank you so much Gayle!

[@shamassive]

Upvoting this as the only positive and thankful answer in the entire comments thread :P

[@luis-azanza]

shamassive thanks a lot! It was helpful to me.

[@avatar098]

I have a bachelors in Computer Science and this still has been incredibly helpful in keeping my fundamentals sharp!

[@TranceDaNight8]

Great video, can I ask what tools did you use for the graphics and drawings ?

[@mayankgupta2543]

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.

[@stevenwilt4450]

@@mayankgupta2543 Only if you read everything literally, which is misunderstanding the language.

[@codingwithike8887]

This video is extremely well done!

[@VaibhavSharma-zj4gk]

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.

[@JeffPohlmeyer]

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?

[@SergioGomez-qe3kn]

@@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.

[@johnaweiss]

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.

[@GeoPoly55]

Mam please produce more videos

[@hueguy]

Thank you for making it so easy to understand !

[@blakete]

Great explanation. Thank you!

[@leikolaboeproduction5785]

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?!

[@DadBodSwagGod]

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

[@younicornyolo4767]

Why the recursive version of the second problem is O(2^(n^2))) ??

[@frankbraker]

7:37 Can anyone tell me why is the simple approach O(2^(n^2)) please?

[@g01dHaCkEr]

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.

[@VigneshDhakshinamoorthy]

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.

[@thegreatlazydazz]

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)

[@starblazer13]

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.

[@QuiqueZapata]

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

[@medievalogic]

Yes but what if you were spawned that those squares ? The number suggests how many paths are there if you start from there.

[@Tiecongli]

Recursion approach with just down/right direction wont' work, you have to try all directions for some cases. But the second DP one brilliant

[@junelikedamonth]

Had the same thought process. Happy that I'm not alone.

[@lolsopal]

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

[@swapnik1000]

Amazing explanation!

[@flamess007]

6:40 that hit me , I was on a coding challenge and couldn't finished on time cause I put i and j wrong

[@mohammadzeqlam5098]

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 .

[@georgeb8637]

6:08 Code example countPaths(grid, row+1) + countPaths(grid, row, col+1)

[@domicio1577]

What is dynamic programming?

[@guess1985]

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?

[@xitrumch]

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

[@DailtonR]

Yeah this stumped me for a minute until I realized it's not correct

[@xitrumch]

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]; } }

[@RajeevSoni007]

@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.

[@Badboys6Reborn]

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?

[@CyberMew]

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?

[@xiao2634]

For the last example at 7:50, can you count and fill the matrix from the top left to the bottom right?

[@aniruddhashevle]

Thank you so much, you really enlightened my way!

[@karimzuniverse]

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.

[@davidbarth80]

any good books that is leading one into problemsolving and problemsolving techniques? Cheers

[@matthewmullin2626]

Her book obviously, Cracking the Coding Interview

[@davidbarth80]

I'm not sure if it would suit a complete beginner in algorithms.

[@samuelasanderinos1521]

Try Grokking Algorithms

[@sfitz219]

Think like a programmer by V. Anton Spraul

[@videovideoguy]

Good explanation of memoization !!!

[@angelosorte1]

2:37 is not even fib(1) already computed?

[@sundarb6673]

Thank you, Gayle!

[@charlliemurphy8381]

Reading her book now. Pretty informative.

[@hryhoriiliashenko906]

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); } }

[@SergioGomez-qe3kn]

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.

[@Kaasbaas1234]

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

[@klarnorbert]

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)

[@Glicerol]

What about loops? Why do you assume you can only go to the bottom or right?

[@dev-skills]

space complexity of recursive solution for fibonacci series very well explained.

[@bprincepandey]

Thanks for this video.

[@abdoulbarry8111]

Best videos eveeerrr!! Matrix problems I just use i and j.

[@vertigo6982]

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

[@michaelstueben2880]

Excellent video. Thanks.

[@rydmerlin]

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.

[@quickbitesitsme]

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) ?

[@wootsat]

G lakshmeepathi how many cells are in an nxn grid? n^2 cells.

[@sauragra]

Very well explained. Thanks.

[@korinostream]

your concepts are banging stars!!!!! (y)

[@ayushigupta4041]

Which software are they using for writing the text in the video?

[@swapnik1000]

Wouldn't this break if there were enough blocks requiring the path to go up or left?

[@mazenkenjrawi158]

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 *_*

[@shinigamiraito42]

Because she isn't teaching Java. She is teaching algorithms. It just so happens to be that most people are familiar with Java syntax.

[@tesukim4338]

Are the background books sponsors? '코딩인터뷰 완전분석' It doesn't seem like the Korean book is there for you to read.

[@The64v]

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.

[@dominicholmes4711]

she explains it pretty clearly at 4:16

[@deputyVH]

I didn't understand the iterative approach. What if you need to back track or side track? Then the number of paths are increased.

[@GPCTM]

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

[@yetAnotherPlus]

Best Teacher, thanks

[@anbansal2k]

Can the memo array be initialised with 0 and 1 and then the 2 ifs be removed?

[@mickeykutti5165]

What do the words associative arrays , lookup table,cache hit/miss ratio have in common with memoization?

[@wmumbra]

Подборка книг на фоне впечатляет ;)

[@J1MKAKA1N]

"Карьера программиста" - наши и там корни пустили :)

[@somechanel]

Gayle - это Галя чтоли?)

[@DragonStoneCreations]

Is this a Breadth First Traversal ?

[@mahithbhima2064]

Is this an official HackerRank channel?

[@edwardhoffenheim3249]

Wouldn't the value at 7, 7 never be added as the recursion can't reach it?

[@DarthTofu2]

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

[@martinza-ch]

What Kind of Illustration program is she using for the presentation?

[@TylerShawful]

I want to know this as well, doing a quick google search didnt come up with much

[@amateruss]

Paint

[@isaacpak1628]

Could someone explain the condition of paths[row][col] == 0 in the memoization solution?

[@SoReaICru]

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.

[@rovsenhuseynov8368]

very useful video. Thanks

[@thatoneuser8600]

4:25 define "path"?

[@dataman4503]

0:38. I usually call it 'Fibo Six'.

[@ShayAxelod22]

Sooo..... What is dynamic programming?

[@andrycanel6169]

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.

[@tomyang7788]

at 7:30 why do we have to check if paths [row][col] == 0 ?

[@amateruss]

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.

[@michaelbrooks6713]

Great job, Thanks for your sharing!!!

[@johnygator]

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.