Algorithms: Memoization and Dynamic Programming

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.

Is this how you play minesweeper?

Garbage explaining for someone who’s never seen this before.

ATTENTION! Her code is WRONG. HERE is what correct memoization looks like.


function fibonacci(n, memo)
if memo[n] is not None
return memo[n]
if n <= 1
f = 1
else
f = fibonacci(n-1, memo) + fibonacci(n-2, memo)
memo[n] = f
return f

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

how is the sapce compelxity for recurive fibonnaci O(N) !??!?!

can anyone show me the working code of the path counting porblem using DP?

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

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?

Thanks! Very clear explanation.

how can Memoization help if your input is > 1000 ...

Awesome video in illustrating difficult concepts

Thanks for this video.

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

Great explanation. Thank you!

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

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

Forgotten to write:
if (row > max || col > max) return 0;
otherwise row and col keep increasing and will buffer overflow

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.

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

Amazing explanation!

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

I deadass thought you just pronounced 'memorization' incorrectly and was very confused for a sec.

You are such an amazing teacher!!

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

Honestly you cant learn dynamic programming

Нормально перевели, "карьера программиста"...

Using the explicit formula for fibonacci numbers, you can implement it in O(log n) time.

So what was the last part going from bottom-up about? Is it just running the example or showing us a different way to do code it?

Best as always, Gayle Laakmann.

kap'epa npogpammucta

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

Good explanation of memoization !!!

Would have been nice to see the explanation of adding in the memo array

Thank you for making it so easy to understand !

Thank you so much, you really enlightened my way!

Grt online teacher

This video is extremely well done!

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

I know she is famous for her book, but she should not be doing these videos if she’s just going to phone it in. Get someone who can present clearly instead.

Ok nanti aku cari di google ya, makasi ya lucifer ,

Gak keliaaataaannnn bapaaakkk 🤣

Gak keliatan ... ketutupan translate ...
Benerin 🤣ayok cepet !

Dp = sub problems