| /** | |
| 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)) |