淘先锋技术网

首页 1 2 3 4 5 6 7

关于斐波那契数列的优化

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

记录一下怎么优化

代码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;
    }
};

在这里插入图片描述