Fibonacci and Dynamic Programming

An exercise for my own understanding of dynamic programming.

The Problem

Finding the N^th Fibonacci number is a classic problem in programming. Starting at 0, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The N^th number is the sum of the two numbers before it. In all the media I've seen, it's solved first recursively and then with dynamic programming.

The Recursive Solution

The recursive solution is the most straightforward. Unfortunately, it's also the least efficient. The function calls itself twice for every number in the sequence. This means that the time complexity is O(2ⁿ), which is terrible. Here's the code:

function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

The reason for the slowness is the function breaks off into two more every time it's called. Alongside this issue, it ends up doing a lot of duplicate work. fibonacci(3) calls for fibonacci(1), and fibonacci(2). In fibonacci(2), we call for fibonacci(1) again. This gets worse as the number gets larger.

The Same But With Caching

The first step (they'll say), is to cache the results of the function. This way, we don't have to recalculate the same numbers over and over again. This is the first step towards dynamic programming. Here's the code:

let cache = {};
 
function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else if (cache[n]) {
    return cache[n];
  } else {
    cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return cache[n];
  }
}

Now the time complexity is O(n). This is because we only have to calculate each number once. The space complexity is also O(n), because we have to store the results of each number. There are ways to reduce the space complexity that I've seen, but it's reasonable for now.

Still, this feels a little backwards, doesn't it? We start counting down from the input number, and that's what caused the extra work in the first place. I believe this is where the dynamic programming gets it's name. Too early to tell. This is only my first post and exploration into the topic.

The Dynamic Programming Solution

Really, we only need to keep the last two solved fibonacci numbers. We can use these to calculate the next one; repeating the process until we reach the N^th number. We can also seed it with the first two numbers to simplify the meat of the code.

function fibonacci(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    let last = 0;
    let current = 1;
 
    for (let step = 2; step <= n; step += 1) {
      let next = last + current;
      last = current;
      current = next;
    }
 
    return current;
  }
}

I want to say this solution is hidden by the way the problem tends to be phrased. However, I have knowledge now that I didn't before, and so it's impossible for me to tell. I feel like a lot of interview questions end up getting phrased that way. They always seem to me like the solution went in search of a problem. Maybe that means the solution is obvious when you get the problem right. Wouldn't that be nice.