https://leetcode.com/problems/climbing-stairs/

climbingStairs.js

/**
 * @param {number} n
 * @return {number}
 */
// brute force backtracking
// O(2^n) time and O(n) space
var climbStairs = function(n) {

    const r = (step) => {
        if(step > n) return 0;
        if(step === n) return 1;
        return r(step + 1) + r(step + 2);
    };

    return r(0);
};

// memoized O(n) space O(n) time
var climbStairs = function(n) {
    
    const memo = new Array(n).fill(-1);

    const r = (step) => {
        if(step > n) return 0;
        if(step === n) return 1;
        if(memo[step] !== -1) return memo[step];
        return memo[step] = r(step + 1) + r(step + 2);
    };

    return r(0);
};

// bottom up O(n) space O(n) time
var climbStairs = function(n) {
    
    const memo = new Array(n).fill(1);
    
    for(let i=n; i>=0; i--){
        if(i === n) memo[i] = 1;
        else if(i === n-1) memo[i] = 1;
        else memo[i] = memo[i+1] + memo[i+2];
    }
    
    return memo[0];
};

// bottom-up O(1) space
var climbStairs = function(n) {

    if(n === 1) return 1;
    if(n === 2) return 2;

    let step = 2;
    let twoAgo = 1;
    let oneAgo = 1;

    let result = 0; // placeholder

    while(step++ <= n){
        result = twoAgo + oneAgo;
        twoAgo = oneAgo;
        oneAgo = result;
    }

    return result;
};