每日刷题_牛客_斐波那契数列(非递归)

ps 这道题可能都被当例子讲烂了。不过在这里用这个我是为下一个题做铺垫

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

主要思路

斐波那契数列：0 1 1 2 3 5 …(f(n-2)+f(n-1))
即在第三项及之后的每一项。都是它的n-1项 + n-2项。所以你可能想过了递归。但是很遗憾的告诉你传统的递归时间复杂度太大。就拿这个题来说。用传统递归系统都不会允许你提交
当然你也可以改装一下，适当降低开销。

传统递归：
 function Fibonacci(n) {
            // write code here
            //在什么时候停止呢，肯定是第二项呗。第二项为1,第一项为0
            if (n <= 1) {
                return n;
            }
            //第n项等于n-1项+n-2项
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }

我的代码

利用数组辅助。用循环来做O（n）的时间复杂度还是可以接受的

function Fibonacci(n)
{
    // write code here
    if(n==0){
       return 0; 
    }
    if(n==1){
        return 1;
    }
       let arr = [];
       arr[0]=0;
       arr[1]=1;
    for(let i=2;i<=n;i++){
        arr[i]=arr[i-1]+arr[i-2]
    }
    return arr[arr.length-1];
    
}