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.
xxxxxxxxxx22
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
