https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

fib.js

// Overlapping Subproblems and Optimization

// https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/
// Example: Fibonacci Numbers, there are many subproblems which are solved again and again.
function fib(num) {
  if (num <= 1) {
    return num;
  }
  return fib(num - 1) + fib(num - 2);
}
// fib(5), fib(4) + fib(3), fib(3) + fib(2), fib(2) + fib(1)...
console.log(fib(5));

// a) Memoization (Top Down)
let mem = {};
function fibMem(num) {
  if (typeof mem[num] === 'undefined') {
    if (num <= 1) {
      mem[num] = num;
    } else {
      mem[num] = fibMem(num - 1) + fibMem(num - 2);  
    }
  }
  return mem[num];
}
console.log(mem); // mem is an Object that has {0:0, 1:1, 2:1, 3:2, 4:3, 5:5}
console.log(fibMem(5));

// b) Tabulation (Bottom Up)
function fibTab(num) {
  let f = [];
  f[0] = 0;
  f[1] = 1;
  let idx;
  for (idx = 2; idx <= num; idx++) {
    f[idx] = f[idx - 1] + f[idx - 2];
  }
  return f[num];
}
console.log(fibTab(5));