Memoization: One Dictionary Cuts 11 Million Calls to 65

How does one dictionary that remembers answers already computed collapse eleven million Fibonacci calls into sixty-five?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Compute it once, then store it

The memo d arrives in the state the video starts it in: the two base cases, and nothing else. Fibonacci of 3 is not in it yet.

Work out Fibonacci of 3 from the two values already sitting in d — build it out of the stored entries rather than typing the answer as a literal — then store it in d under the key n. Assign the updated dictionary to memo.

# Exercise 1: add the entry for Fibonacci of n to the memo.
d = {1: 1, 2: 1}
n = 3

# your code here

memo = d  # the updated memo

# Exercise 1: add the entry for Fibonacci of n to the memo.
d = {1: 1, 2: 1}
n = 3

# your code here

memo = d  # the updated memo

Python runs in your browser

⌘/Ctrl + Enter runs

is a dictionary

still holds the two base cases

has an entry under the new key

the new entry is built from the two already stored

adds exactly one entry

←Previous fib_recur: Two Recursive Calls and an Exploding Call Tree Next Counting Basketball Scores: Three Base Cases, Three Branches →