Last active
November 28, 2017 19:22
-
-
Save mauris/b1f5f4373259dedbc25c534d1f6d1058 to your computer and use it in GitHub Desktop.
Fibonacci Dynamic Programming
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// The mathematical definition (i.e. simple recursion): | |
function fib(n) { | |
if (n < 1) { // base case 1 | |
return 0; | |
} | |
if (n < 3) { // base case 2 | |
return 1; | |
} | |
// recursion steps | |
return fib(n - 1) + fib(n - 2); | |
} | |
// But we notice that fib has overlapping solutions, i.e. fib(n - 1) will also later call fib(n - 2). | |
// that is inefficient. We can store previously the calculated results in a table (memoization table). | |
// Spelling of memoization is correct. | |
let memo = {}; | |
function fib(n) { | |
if (n < 1) { // base case 1 | |
return 0; | |
} | |
if (n < 3) { // base case 2 | |
return 1; | |
} | |
if (memo[n]) { // check if previously calculated value is available. | |
return memo[n]; | |
} | |
// branches of function calls to repeated values | |
// are pruned away | |
// recursion steps | |
let result = fib(n - 1) + fib(n - 2); | |
memo[n] = result; | |
return result; | |
} | |
// The example above is a top-down approach (you start from n and work your way down to the base cases). | |
// let us take a look at the bottom-up version of the code: | |
function fib(n) { | |
// result already contain base cases | |
let result = [0, 1]; | |
for (let i = 2; i < n + 1; ++i) { // for i = 2 to n | |
// at the time we calculate the addition, (i - 1)th and (i - 2)th numbers are already available. | |
// we always add new number at the end of the array | |
// array will grow to the n-th number. | |
result.push(result[i - 1] + result[i - 2]); | |
} | |
return result[n]; | |
} | |
// the bottom up approach may be faster that the top down version since there | |
// is less overhead of the function calls (no recursion). | |
// however, some solution may not be straightforward enough to build a bottom up version easily | |
// or a bottom-up solution may not exist |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment