✅509. 斐波那契数 about like-algorithms HOT 2 OPEN

// 解法一：top -> down
var fib = function (N) {
    if (N <= 1) return N;

    let memo = [];
    memo[0] = 0;
    memo[1] = 1;

    function momoize(number) {
        if (memo[number] !== undefined) return memo[number];
        return momoize(number - 1) + momoize(number - 2);
    }

    return momoize(N);
};

// 解法二：down -> top
var fib = function (N) {
    if (N <= 1) return N;

    let memo = [];
    memo[0] = 0;
    memo[1] = 1;

    for (let i = 2; i <= N; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }

    return memo[N];
};

// 解法三：解法二优化
var fib = function (N) {
    if (N <= 1) return N;

    let prev2 = 0;
    let prev1 = 1;
    let result = 0;

    for (let i = 2; i <= N; i++) {
        result = prev1 + prev2;
        prev2 = prev1;
        prev1 = result;
    }

    return result;
};

var fib = function(N) {
    if (N === 0) return 0;
    if (N === 1 || N === 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    const dp = [0, 1, 1];
    for (let i = 3; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
};

var fib = function(N) {
    if (N === 0) return 0;
    if (N === 1 || N === 2) return 1;
    let pre = 1;
    let cur = 1;
    for (let i = 3; i <= N; i++) {
        const sum = cur + pre;
        pre = cur;
        cur = sum;
    }
    return cur;
};