Skip to content

Instantly share code, notes, and snippets.

@djleonskennedy
Last active September 15, 2020 07:18
Show Gist options
  • Save djleonskennedy/daa9467a4b76b62c9ecad1fa4eb0abfd to your computer and use it in GitHub Desktop.
Save djleonskennedy/daa9467a4b76b62c9ecad1fa4eb0abfd to your computer and use it in GitHub Desktop.
Dynamic Programming example
function fib(n) {
if(n === 1 || n === 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
function fibMemo(n , memo) {
if(memo.get(n)) {
return memo.get(n);
}
if(n === 1 || n === 2) {
return 1;
}
const result = fib(n - 1) + fib(n - 2);
memo.set(n, result);
return result;
}
function fibBottomUp(n) {
if(n === 1 || n === 2) {
return 1;
}
const bootomUp = new Array(n+1)
.fill(0)
.map((_, i) => i);
bootomUp[0] = 1;
bootomUp[1] = 1;
for(let i = 3; i < bootomUp.length; i++) {
bootomUp[i] = bootomUp[i-1] + bootomUp[i-2]
}
return bootomUp[n];
}
function fibBottomUpV2(n) {
let a, b, result;
if(n === 1 || n === 2) {
return 1;
}
a = b = 1;
for (let i = 3; i <= n; i++)
{
result = a + b;
a = b;
b = result;
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment