Identify the Subproblems
The subproblems are just the recursive calls of fib(n-1)
and fib(n-2)
. We know that fib(n)
is the nth Fibonacci number for any value of n so we have our subproblems.
With our subproblems defined, let's memoize the results. This means we're going to save the result of each subproblem as we compute it and then check before computing any value whether or not its already computed. However, this will only require tiny changes to our original solution.
xxxxxxxxxx
22
function fib(n) {
if (n < 2) return n;
​
// create cache and initialize it to -1
let cache = new Array(n + 1).fill(-1);
​
// fill initial values
cache[0] = 0;
cache[1] = 1;
return fibHelper(n, cache);
}
​
function fibHelper(n, cache) {
// if the value is in the cache return it
if (cache[n] >= 0) return cache[n];
​
// else compute the result and add it to the cache
cache[n] = fibHelper(n - 1, cache) + fibHelper(n - 2, cache);
return cache[n];
}
​
console.log("fib(5) =", fib(5));
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment