Dynamic Programming — Recursion, Memoization and Bottom Up Algorithms
InterviewCake is a funny place. This morning I had a question which I’ve seen many times before. “Write a function that that computes the nth fibonacci number”. Let’s break this problem down. First off, what’s a fibonacci number? A fibonacci number is a series of numbers in which each number is the sum of the two preceding numbers.
Classic recursion problem right? What’s our base case…if the number is 0 or 1, return the number, else return the previous sums recursively. The code looks like this:
function fib(n){
if(n === 0 || n === 1){
return n;
}
return fib(n - 2) + fib(n - 1);
}The question though, is what’s the time complexity of this? My first thought was O(n) right, if n was 5 it’ll compute fib(5), fib(4), fib(3). But it won’t! If n was 5, it’ll computer fib(4) AND fib(3), then fib(4) will compute fib(3) and fib(2), fib(3) computes fib(2) and fib(1). That certainly isn’t O(N), that’s a binary tree. With a binary tree, the total number of nodes is O(2^N), and to sort through is not a friendly time complexity! To sort through an an ordered binary tree we could binary search…but that’s another problem for another day. Take a look at the O(2^n), not good!


So how can we solve this problem in less time? It’s time to learn memoization!
Defined by InterviewCake, memoization ensures that a function doesn’t run for the same inputs more than once by keeping a record of the results for given inputs(usually in an object).
We create an object, memo, then we follow two steps:
- Check memo to see if we can avoid computing the answer for any given input.
- Save the results of any calculations to memo.
function Fibber(){
this.memo = {};
}Fibber.prototype.fib = function(n){
if(n === 0 || n === 1) {
return n;
}
if(this.memo.hasOwnProperty(n)){
return this.memo[n];
}
this.memo[n] = this.fib(n - 2) + this.fib(n - 1);
return this.memo[n];
}
Let’s go through this where 6 is the input.
new Fibber().fib(6);computing fib(6), which is fib(4) + fib(5)
computing fib(4), which is fib(2) + fib(3)
computing fib(2), which is fib(0) + fib(1)
fib(0) + fib(1) is 1
this.memo[2] = 1;go back up the call stack, but this time we have fib(2) recorded in our hash, so we don’t have to go all the way back down!computing fib(3), which is fib(1) + fib(2)
fib(1) is 1
we grab memo[2] — 1
this.memo[3] = 2
computing fib(4)
we grab memo[2] — 1, add it to memo[3] — 2
this.memo[4] = 3
fib(5) = memo[3] + memo[4]
fib(5) = 2 + 3
this.memo[5] = 5
fib(6) = memo[4] + memo[5]
fib(6) = 3 + 5
this.memo[6] = 8
return 8
Because no node is called more than once, this dynamic programming strategy known as memoization has a time complexity of O(N), not O(2^N). Awesome!

While O(N) time is good, the space complexity can be brought down to O(1). Right now with memoization we need an object the size of N, can we do it without the object? Yes we can, bring in, a bottom up approach!
By starting at 1 and 0, the first two fibonacci numbers, by setting variables and changing these two values, we create the simplest solution yet! If our input is 1 or 0(or negative), we return appropriately. If not, we set a variable, twoBehind to 0, a variable oneBehind to 1, and fib which we’ll eventually return, but be able to use in our variable assignments.
Starting at 1, and while we’re less than n, we assign fib to twoBehind+oneBehind, then move up both values.
function bottomUpFib(n){
if(n === 1 || n === 0){
return n;
} var twoBehind = 0;
var oneBehind = 0;
var fib = 0;
for(var i = 1; i < n; i++){
fib = twoBehind + oneBehind;
twoBehind = oneBehind;
oneBehind = fib;
}
return fib;
}
Look at that guy! Bottoms up!
To recap, dynamic programming comes in three steps:
Recursion — Big O(2^N)
Memoization — O(N) — time, O(N) — space
Bottoms Up — O(N) — time, O(1) — space

