Algorithms

Dynamic_Programming_Fibo.js

/**

 DYNAMIC PROGRRAMMING
    1. Overlapping subproblems
    2. Optimal substructure


 If a problem has above two characteristics,
 it can be solved with dynamic programming.

 Remembering old values
  Solve each problem just once, store the result
  so that it can be resued again.

  - Memorization (top-down)
        usually with recursive
        using array or dictionary data structure ( key - value mapping)
        
  - Tabulation (bottom-up)
        usually with iteration
        using array to store cache, and use for next calculation

 Ref:
 https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13/

*/

let numOfCalls = 0;
let memo = {};

function fib(n) {
    numOfCalls++;

    //base case
    if(n <= 2) return 1;

    if(n in memo) {
        console.log("found in memo",n)
        return memo[n];
    }
    memo[n] =  fib(n-1) + fib(n-2);
    return memo[n];
}
let n= 30;
console.log(`${n} Fibonacci sequence number is (using memorization) `,fib(n))
console.log ("Number of calls",numOfCalls)


function fib_tabulation(n) {
    if(n <=2 ) return 1;
    let arr = [];
    arr[0] = undefined;
    arr[1] = 1;
    arr[2] = 1;
    for(let i=3 ; i<=n; i++) {
        arr[i]=arr[i-1]+arr[i-2]
    }
    return arr[n]
}

n= 30;
console.log(`${n} Fibonacci sequence number (using tabulation) is `,fib(n))