Skip to content

Instantly share code, notes, and snippets.

@remi-bruguier
Created May 22, 2020 20:15
Show Gist options
  • Save remi-bruguier/b536189ea51e0f18fcdf14d98fdefcc1 to your computer and use it in GitHub Desktop.
Save remi-bruguier/b536189ea51e0f18fcdf14d98fdefcc1 to your computer and use it in GitHub Desktop.
// no recursion
const waysToClimbStairs = (n:number):number => {
const a:number[] = [1,1];
if(n>1){
for(let i = 2; i <= n ; i++){
a[i] = a[i-1] + a[i-2];
}
};
return a[a.length - 1];
}
// with recursion
const waysToClimbStairsRecursive = (n:number):number => {
if (n < 0) return 0;
if (n === 0) return 1;
return waysToClimbStairsRecursive(n - 1) + waysToClimbStairsRecursive(n - 2);
}
// with recursion, but memoized
const waysToClimbStairsRecursiveMemoized = (n:number, m:{ [key: number]: number } = {}):number => {
if (n < 0) return 0;
if (n === 0) return 1;
if(m[n]) return n;
return m[n] = waysToClimbStairsRecursiveMemoized(n - 1) + waysToClimbStairsRecursiveMemoized(n - 2);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment