70. Climbing Stairs

Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Solution

Solution 1

/**
 * Find the possible solutions of combinations for x + 2y = n
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    "use strict";
    function combination(x, y) {
        let result = 1;
        let i = y;
        while (i) {
            result *= x;
            x--;
            i--;
        }
        while (y) {
            result /= y;
            y--;
        }
        return result;

    }
    let sum = 0;
    // x can either start from 0 or 1
    // depends on if there are even/odd number of stairs
    for (let x = n % 2; x <= n; x += 2) {
        let y = (n - x) / 2;
        sum += combination(x+y, y);
    }
    return sum;
};

Solution 2

/**
 * Solved with Fibonacci numbers (Dynamic Programming approach)
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    "use strict";
    let table = {};
    function fibonacci(n) {
        if (table[n]) {
            return table[n];
        }
        if (n === 1 || n === 2) {
            return n;
        }
        table[n] = fibonacci(n-1) + fibonacci(n-2);
        return table[n];
    }
    return fibonacci(n);
};