题目描述

要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n<=39

思路

递归法的时间复杂度以n的指数的方式递增，而且有很多的重复计算，效率太慢
可以采用循环的方法，从下往上依次计算
f1,f2,f3
f3=f1+f2;
f1=f2;
f2=f3;

代码

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0||n==1)
            return n;
        int f1=0;
        int f2=1;
        int f3=0;
        for(int i=0;i<n-1;i++)  //循环n-1次
        {
            f3=f1+f2;
            f1=f2;
            f2=f3;
        }
        return f3;

    }
};