Dynamic Programming example

fib_dynamic_programming.js

function fib(n) {
  if(n === 1 || n === 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

function fibMemo(n , memo) {
  if(memo.get(n)) {
    return memo.get(n);
  }
  if(n === 1 || n === 2) {
    return 1;
  }
  const result = fib(n - 1) + fib(n - 2);
  memo.set(n, result);
  return result;
}

function fibBottomUp(n) {
  if(n === 1 || n === 2) {
    return 1;
  }
  const bootomUp = new Array(n+1)
  .fill(0)
  .map((_, i) => i);

  bootomUp[0] = 1;
  bootomUp[1] = 1;
  for(let i = 3; i < bootomUp.length; i++) {
    bootomUp[i] = bootomUp[i-1] + bootomUp[i-2]
  }
  return bootomUp[n];
}

function fibBottomUpV2(n) {
  let a, b, result;

  if(n === 1 || n === 2) {
    return 1;
  }

  a = b = 1;

  for (let i = 3; i <= n; i++)
  {
    result = a + b;
    a = b;
    b = result;
  }

  return result;
}