Memoization

Prereq: Backtracking

Memoization is a fancy word for a simple concept (so is the case for a lot of things we learn at school). It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again. And no I didn't spell it wrong. The word is meant to mean writing down on a "memo".

A classic example is calculating Fibonacci number.

1def fib(n):
2    if n == 0 or n == 1:
3        return n
4    return fib(n - 1) + fib(n - 2)
5

This results in a lot of repeated computations

The solution is simply saving previous results in a map of function arguments to results (the "memo"), checking it, and returning previous results if it has been done before. Otherwise, we carry out the computation and save the results in the map.

1def fib(n, memo):
2    if n in memo: # check in memo, if found, retrieve and return right away
3        return memo[n]
4
5    if n == 0 or n == 1:
6        return n
7
8    res = fib(n - 1, memo) + fib(n - 2, memo)
9
10    memo[n] = res # save in memo before returning
11    return res
12

Memoization is particularly useful for combinatorial problems that have large repeated state-space tree branches. We will see that in the next module.