/**
 * Brute Force - DFS
 * Time O(2^N) | Space O(N)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
 var climbStairs = (n, index = 0) => {
    const isBaseCase1 = (n < index);
    if (isBaseCase1) return 0;

    const isBaseCase2 = (index === n);
    if (isBaseCase2) return 1;

    const [ next, nextNext ] = [ (index + 1), (index + 2) ];
    const left = climbStairs(n, next);     /* Time O(2^N) | Space O(N) */
    const right = climbStairs(n, nextNext);/* Time O(2^N) | Space O(N) */

    return (left + right);
}

/**
 * DP - Top Down
 * Array - Memoization
 * Time O(N) | Space O(N)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
var climbStairs = (n, index = 0, memo = Array(n + 1).fill(0)) => {
    const isBaseCase1 = (n < index);
    if (isBaseCase1) return 0;

    const isBaseCase2 = (index === n);
    if (isBaseCase2) return 1;

    const hasSeen = (memo[index] !== 0);
    if (hasSeen) return memo[index];

    const [ next, nextNext ] = [ (index + 1), (index + 2) ];
    const left = climbStairs(n, next, memo);     /* Time O(N) | Space O(N) */
    const right = climbStairs(n, nextNext, memo);/* Time O(N) | Space O(N) */

    memo[index] = (left + right);                /*           | Space O(N) */
    return memo[index];
};

/**
 * DP - Bottom Up
 * Array - Tabulation
 * Time O(N) | Space O(N)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
var climbStairs = (n) => {
    const isBaseCase = (n === 1);
    if (isBaseCase) return 1;

    const tabu = initTabu(n);/* Space O(N) */

    search(n, tabu);

    return tabu[n];
};

var initTabu = (n) => {
    const tabu = new Array(n + 1).fill(0);

    tabu[1] = 1;
    tabu[2] = 2;

    return tabu;
}

var search = (n, tabu) => {
    for (let index = 3; (index <= n); index++) {/* Time O(N) */
        const [ prev, prevPrev ] = [ (index - 1), (index - 2) ];

        tabu[index] = (tabu[prev] + tabu[prevPrev]);/* Space O(N) */
    }
}

/**
 * DP - Fibonacci Number
 * Time O(N) | Space O(1)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
var climbStairs = (n) => {
    const isBaseCase = (n === 1);
    if (isBaseCase) return 1;

    let [ next, nextNext ] = [ 1, 2 ];

    for (let index = 3; (index <= n); index++) {/* Time O(N) */
        const temp = (next + nextNext);
        
        next = nextNext;
        nextNext = temp;
    }

    return nextNext;
};

/**
 * Matrix - Bitnets Method
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
 var climbStairs = (n) => {
    const prev = [ [1, 1], [1, 0] ];
    const next = power(n, prev);/* Time O(log(N)) */

    return next[0][0];
}

const power = (n, prev)  => {
    let next = [ [1, 0], [0, 1] ];

    const isEmpty = () => n === 0;
    while (!isEmpty()) {/* Time O(log(N)) */
        const isBit = (n & 1) === 1;
        if (isBit) next = multiply(next, prev);/* Time O(1) | Space O(1) */

        n >>= 1;
        prev = multiply(prev, prev);           /* Time O(1) | Space O(1) */
    }

    return next;
}

const multiply = (prev, next) => {
    const [ rows, cols ] = [ 2, 2 ];
    const matrix = new Array(rows).fill()
        .map(() => new Array(cols).fill(0));

    for (let row = 0; (row < rows); row++) {
        for (let col = 0; (col < cols); col++) {
            const left = (prev[row][0] * next[0][col]);
            const right = (prev[row][1] * next[1][col]);

            matrix[row][col] = (left + right);
        }
    }

    return matrix;
}

/**
 * Math - Fibonacci Formula
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
var climbStairs = (n, sqrt5 = Math.sqrt(5)) => {
    const phi = ((sqrt5 + 1) / 2);
    const psi = ((sqrt5 - 1) / 2);

    const phiPow = Math.pow(phi, (n + 1));
    const psiPow = Math.pow(psi, (n + 1));

    return ((phiPow - psiPow) / sqrt5);
}