js 实现斐波那契数列

O2^N 算法，常规写法，递归实现

代码语言：javascript复制

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

console.log(fib(3)); // 5
console.log(fib(5)); // 8

O(N) 算法，动态规划，重叠子问题

代码语言：javascript复制

function fibonacci(n) { 
    if (n <= 1) return n;
    let fib = [0, 1]; // 保存斐波那契数列的结果 
    for (let i = 2; i <= n; i  ) { 
        fib[i] = fib[i - 1]   fib[i - 2]; // 计算第i个斐波那契数 
    } 
    return fib[n]; 
}
    

参考

console return 递归 动态规划 算法

0 人点赞