Memoization

Memoizaton

Memoization is a concept in dynamic programming that involves storing the results of expensive calls for reuse later. There is no way you can talk about memoization without mentioning caching — the heartbeat of memoization. This involves storing previous results mostly in an object or an array/list.

Whenever I think of memoization, I think of recursion + caching. You’ll often come across memoization in functional programming, as the technique has several use cases. However, two main properties suggest a problem can be solved with memoization.

When to use Memoization

1. Overlapping Subproblems

Overlapping subproblems refers to when the solution of subproblems is needed over and over again. So these solutions are stored in the form of lookup tables to avoid computing them again. The Fibonacci sequence is a great example:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377

Each number is a sum of the previous two, that is if we are to calculate the next Fibonacci number, all we need to do is add the two previous numbers: 233 + 377 = 610 in this case.

2. Optimal Substructure

Optimal substructure means the optimal solution to a larger problem can be deduced from a combination of the optimal solution to its subproblems. Dynamic programming takes advantage of…