你真的会斐波那契数列吗

const rl = require("readline").createInterface({ input: process.stdin });

rl.on('line', (line) => {
    const n = parseInt(line);
    const res = resolve3(n);
    console.log(res);
});

/**
 * 1. 递归的方式
 */
function resolve(n) {
    if(n <= 2) return 1;

    return resolve(n - 1) + resolve(n - 2);
}

/**
 * 2. 带备忘录的递归优化
 */

function resolve2(n) {
    const memory = Array(n+1).fill(0);

    const helper = (n, memory) => {

        if(n <= 2) return 1;

        if(memory[n] !== 0) return memory[n];
        

        memory[n] = helper(n - 1, memory) + helper(n - 2, memory);
        return memory[n];
    }

    return helper(n, memory);
}

/**
 * 3. dp 将递归转成迭代
 */

function resolve3(n) {
    const dp = Array(n + 1).fill(1);

    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

/**
 * 空间优化
 */
function resolve4(n) {
    if(n <= 2) return 1;

    let pre = 1, next = 1, res;

    for(let i = 3; i <= n; i++) {
        res = pre +  next;
        pre = next;
        next = res;
    }
    return res;
}

从斐波那契数列窥探动态规划

递归实现 -> 带备忘录的递归优化 -> 动态规划实现

动态规划的本质还是 穷举，将方式二的递归实现为迭代方式。状态转移方程是关键 dp[i] = dp[i-1] + dp[i - 2]

最后因为后续只用到前两个值，所以可以再把空间优化一下得到解法4。