Algorithms: Memoization and Dynamic Programming

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.

[zingg]

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.

[SteversIO]

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

[ujjvalsharma]

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.

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

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

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

[dmitrys]

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

[sunnilabeouf]

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

[kidou]

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!

[bsingularity]

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

[Seborgium]

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

[jialiliang]

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

[stanst]

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

[BadboysReborn]

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?

[RegularTetragon]

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

[Irwansyah-kqlf]

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

[ififif]

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.

[sebbes]

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?

[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

[Bodyja]

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