斐波那契数列就不用多说了

记录一下怎么优化

代码1：

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=2)
            return 1;
        return  Fibonacci(n-1)+ Fibonacci(n-2);
    }
};

代码2：

class Solution {
public:
    int a[50];
    int Fibonacci(int n) {
        a[1]=1;a[2]=1;
        if(a[n]) return a[n];
        a[n]=Fibonacci(n-1)+ Fibonacci(n-2);
        return a[n];
    }
};

代码3：

class Solution {
public:
    int a[50];
    int Fibonacci(int n) {
        a[1]=1;a[2]=1;
        for(int i=3;i<=n;i++)
            a[i]=a[i-1]+a[i-2];
        return a[n];
    }
};

代码4：

class Solution {
public:
    int Fibonacci(int n) {
        int a=1,b=1,c=1;
        for(int i=3;i<=n;i++)
        {
            c=a+b; a=b; b=c;
        }
        return c;
    }
};