[509] 斐波那契数

类似题目：爬楼梯

递归

details

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

记忆优化

var fib = function (n) {
    let map = new Map();
    return traverse(n);
    function traverse(n) {
        if (n === 0) return 0;
        if (n === 1) return 1;
        map.set(n, fib(n - 1) + fib(n - 2));
        return map.get(n);
    }
};

迭代

details

var fib = function (n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; 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) return 1;
    let prev1 = 0,
        prev2 = 1;

    for (let i = 2; i <= n; i++) {
        let cur = prev1 + prev2;
        prev1 = prev2;
        prev2 = cur;
    }
    return prev2;
};