Skip to content

Instantly share code, notes, and snippets.

@remi-bruguier
Last active May 22, 2020 22:33
Show Gist options
  • Save remi-bruguier/d703dfea4e5f1b7794bd4a231fcd560c to your computer and use it in GitHub Desktop.
Save remi-bruguier/d703dfea4e5f1b7794bd4a231fcd560c to your computer and use it in GitHub Desktop.
// without 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 m[n];
return m[n] = waysToClimbStairsRecursiveMemoized(n - 1, m) + waysToClimbStairsRecursiveMemoized(n - 2, m);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment