interesting-problems/DynamicProgrammingWithClosures.js at main · jaskanwal96/interesting-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// Comparison between recursive and dynamic solution for the fibonacci series

// let start = Date.now();

// function fib(n) {
//     if (n <= 0) return 0;
//     if (n <= 2) return 1;
//     return fib(n - 1) + fib(n -2);
// }
// console.log(fib(44));

// console.log('Time taken for the program to run without DP',(Date.now() - start) / 1000);

// This took 7 seconds for the code to find the 44th element

// Lets Combine Closures and Dynamic Programming

start = Date.now();
function outer() {
    let dp = {};
    function fib(n) {
        if (n <= 0) return 0;
        if (n <= 2) return 1;
        if (dp[n] != undefined) return dp[n];
        dp[n] =  fib(n - 1) + fib(n - 2);
        return dp[n];
    }
    return {fib, dp};
}
const myOuter = outer();
const myNewOuter = outer();
const myFib = myOuter.fib;
console.log(myFib(10));
const myNewFib = myNewOuter.fib;
console.log('Time taken for the program to run with DP:', (Date.now() - start) / 1000);
console.log(myNewOuter.dp);
// Output
// 701408733
// Time taken for the program to run without DP 10.522
// 701408733
// Time taken for the program to run with DP: 0.02