What is memoization?

Stumbling my way through leetcode, I came across a problem in which most solutions implemented memoization. I tried my usual iterative techniques to no avail, and was very curious about this "memo" I kept seeing.

So what is memoization?

Not to get it confused with memorization, a completely different topic that usually doesn't have any place in programming (although, the name is based on memorization!).

Memoization is the technique of storing computed values for quick access in order to speed up slower functions. It is essentially like caching so these stored values won't have to be calculated multiple times.

Here is the wikipedia definition for more clarity:

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Memoization is almost exclusively used with recursion or dynamic programming as a way to significantly decrease the run time of a recursive function. Although dynamic programming doesn't have to include memoization, fairly often they are used synonymously.

Code example

I saw this great example using the Fibonacci sequence so I thought I'd replicate it as I found it incredible for basic understanding.

If you're not familiar with the Fibonacci sequence, it is essentially the sum of the two integers before it in the sequence. It begins with 1 and 1 and continues on from there forever. The first 10 iterations would look like this:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

So this first example is our regular recursive solution for the problem:

def fibonacci(n)
    if n == 1 || n == 2
        result = 1
    else
        result = fibonacci(n-1) + fibonacci(n-2)
    end
    return result
end

If we were to solve this problem with memoization all we'd need to do is create a memo array and store each of the solutions we get from all of our different iterations of n.

def fibonacci(n, memo)
    if memo[n] != nil
        return memo[n]
    end

    if n == 1 || n == 2
        result = 1
    else
        result = fibonacci(n-1, memo) + fibonacci(n-2, memo)
        memo[n] = result
    end
    return result
end

You can see that we added an if statement at the beginning to check if we already have our result for n. If it is saved in our memo array then it's as easy as accessing that index.

Similarly, if we haven't seen the value before we will compute it and then save it into our memo array in the end.

Time complexity

You can imagine that using memoization would have a huge effect on the efficiency of this function. That's really the main benefit anyway! By storing all of our calculated values and avoiding repeat computations, we can reduce the average time complexity from O(n²) to O(n).

Resources

I actually got the code example from this amazing youtube video so please check it out! YK does such an amazing job of explaining the concept I would definitely recommend watching it if dynamic programming is new to you.

I also found this article super helpful and thought it breaks down memoization into something more digestible.

That's all I've got for today but I hope this explanation could be helpful to you! As always, please leave comments with your thoughts 😊