Memoization is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs. It is the top-down approach to solving a problem with dynamic programming.
It’s called memoization because we will create a memo, or a “note to self”, for the values returned from solving each problem.
Then, when we encounter the same problem again, we simply check the memo, and, rather than solving the problem a second (or third or fourth) time, we retrieve the solution from our memo.
Top-Down Fibonacci
Here’s our Fibonacci sequence, memoized:
const fibDown = (n, memo=[]) => {
if (n == 0 || n == 1) {
return n;
}
if (memo[n] == undefined) {
memo[n] = fibDown(n - 1, memo) + fibDown(n - 2, memo);
}
return memo[n];
}