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. 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 argument to results (the "memo") and 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.