If you read my post last week about tabulation, one of two dynamic programming (DP) strategies used to break down a problem into similar and smaller subproblems, then you know this post is a follow up about its sister strategy: memoization. Also, the post title is another giveaway about the wonders of memoization. Alas, the destination of this post is not a tropical vacation.
Memoization
Memoization is a recursive DP strategy that utilizes a hash map to store the results of the subproblems ((since this will be written in JavaScript, I’ll refer to this as an object going forward). The object is typically referred to as the memo (hence the moniker memoization!) and acts as a cache, and any subsequent calls to it will simply fetch the stored result in constant time.
Leetcode: Fibonacci
To illustrate memoization, I’ll walk through the following Leetcode problem and classic code challenge: Fibonacci.
The Fibonacci numbers, commonly denoted F(n) form a sequence,
called the Fibonacci sequence, such that each number is the sum of
the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).
Example 1:
Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1
Example 2:
Input: 5
Output:
Explanation: F(5) = F(4) + F(3) = 3 + 2 = 5
Set Up Your Memo
As we’ll build a recursive function, we will want to pass in a memo object as an additional argument to the function.
function fibonacci(n, memo = {}) {
//
}
The keys in the object will represent unique arguments passed to the function, and the values will represent the result for those arguments. In this specific problem, the keys will be numbers going up to and including n.
Add a Base Case Condition
All recursive functions need a base case that will ultimately halt the recursion and exit the function (otherwise we would enter into an infinite loop) and a recursive step where we continue the recursion by making another call.
The base case condition will return the stored value in the object if the function’s argument is in the memo (exists as a key).
if (n in memo) return memo[n];
This is also a good time to take care of edge cases if n === 0 or n === 1.
if (n === 0 || n === 1) return n;
Recursive Call and Storing the Results
Before we return the result of the recursive call, we’ll want to store it in the memo. The efficiency of memoization is with the lookup of the previous subproblem’s result, instead of having to recompute the same problem again.
function fibonacci(n, memo = {}) {
if(n in memo) return memo[n];
if (n === 0 || n === 1) return n;
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
Time and Space Complexity
The above method uses O(n) time and space.
I hope you found this helpful. If you want to learn more about memoization, do check out the materials below. Happy coding!
Top comments (0)