Fibonacci Dynamic Programming

fib.js

// The mathematical definition (i.e. simple recursion):

function fib(n) {
  if (n < 1) { // base case 1
    return 0;
  }
  if (n < 3) { // base case 2
    return 1;
  }
  // recursion steps
  return fib(n - 1) + fib(n - 2);
}

// But we notice that fib has overlapping solutions, i.e. fib(n - 1) will also later call fib(n - 2).
// that is inefficient. We can store previously the calculated results in a table (memoization table).
// Spelling of memoization is correct.

let memo = {};

function fib(n) {
  if (n < 1) { // base case 1
    return 0;
  }
  if (n < 3) { // base case 2
    return 1;
  }
  
  if (memo[n]) { // check if previously calculated value is available.
    return memo[n];
  }
  // branches of function calls to repeated values
  // are pruned away
  
  // recursion steps
  let result = fib(n - 1) + fib(n - 2);
  memo[n] = result;
  return result;
}

// The example above is a top-down approach (you start from n and work your way down to the base cases).
// let us take a look at the bottom-up version of the code:

function fib(n) {
  // result already contain base cases
  let result = [0, 1];
  for (let i = 2; i < n + 1; ++i) { // for i = 2 to n
    // at the time we calculate the addition, (i - 1)th and (i - 2)th numbers are already available.
    // we always add new number at the end of the array
    // array will grow to the n-th number.
    result.push(result[i - 1] + result[i - 2]);
  }
  return result[n];
}

// the bottom up approach may be faster that the top down version since there
// is less overhead of the function calls (no recursion).

// however, some solution may not be straightforward enough to build a bottom up version easily
// or a bottom-up solution may not exist