climbing-stairs.js

/*
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:
 - 1 <= n <= 45
*/
// solution
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const cache = {};
    
    return calc(n);
    
    function calc(step) {
        if (cache[step]) {
            return cache[step];
        }
        
        if (step === 1) {
            return 1;
        } else if (step === 2) {
            return 2;
        }
        cache[step] = calc(step - 1) + calc(step - 2);
        return cache[step];
    }
};

// the best solution I liked
var climbStairs = function(n) {
    let a = 1, b = 2, next;
    
    for(let i = 3; i <= n; i++) {
        next = a + b;
        a = b;
        b = next;
    }
    return n === 1 ? a : b;
};