Memoization

What is Memoization?

Memoization is the most popular cache method used in Competitive Programming. It uses the simple laws of caching which is using a dictionary to store data and keys and using the values of keys in the dictionary as the return values of the function.

Simple Memoization Implementation

Here's the fibonacii example from the Recursion tutorial:

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

With this code, we can reach higher values if we run lower values of the function first. We only use simple if-statements to check if values are cached and we return them if they are. Otherwise, we calculate values and cache them.

Built-in Cache Methods in Python

In the example above,