Bottom Up vs Top Down Dynamic Programming vs Recursion | Fibonacci Sequence

In this video we look at the performance problems that occur when using recursion with reference to the Fibonacci Sequence. To address this we look at top down dynamic programming (memoization) and bottom up dynamic programming (tabulation) and compare and contrast their respective pros and cons.

[algorithmswithbrenton]

Important correction for a mistake pointed out by Vijay below, sorry for that - unfortunately I don't seem to be able to edit this part and I have decided against cutting it out as the general idea is still explained.

The memoized code with the cache does not correctly use the cache for recursive calls, the simplest way to fix it is probably by passing around the cache and defaulting it for the initial call.

def fib_memoized(n, cache={}):
if n <= 1:
return n
elif n in cache:
return cache[n]
else:
return fib_memoized(n-1, cache) + fib_memoized(n-2, cache)

[picnicbros]

I dont know why a video with this quality is so underrated. Good job!

[ChrisSchepman]

Career programmer of 15+ years and I'm still learning! Excellent video.

[slimanimeriem]

such a greaat video, simple, concise and gives all the needed basics. Thank you!

[malifraz]

Great video, excellent explanation. James Zheng needs to watch this.

[j.r.]

This is such a good video - extremely clear and concise

[footballeditzs]

Great work, you desrerve more views for this work

[nasimnajand]

thanks for visualization and nice explanation

[VijayPatel-xlfm]

Can you explain the code at 3:09? Not sure how the cache does something in that situation because its not being used in the fib() function for repeated calls.

*def fib_memo(n):*
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
cache = {}
if n not in cache:
cache[n] = fib(n)
return cache[n]

[amirafauzey]

Can you make videos solving leetcode pleaseeee