题解 | #斐波那契数列#

第四十二题 都懒得写 和42一模一样

非递归

class Solution {
public:
    int Fibonacci(int n) {
        // 两种 一种递归 一种非递归
        // 非递归效率高
        if(n==1||n==2)
            return 1;
        int *a=new int[n];
        a[0]=1;
        a[1]=1;
        for(int i =2;i<n;i++)
            a[i]=a[i-1]+a[i-2];
        return a[n-1];
    }
};

递归

class Solution {
public:
        // 记录已经被计算出来的值
    map<int,int> map_flag;
    int Fibonacci(int n) {
        // 两种 一种递归 一种非递归
        // 递归
        if(n==1||n==2)
            return 1;
        if(map_flag.count(n))
            return map_flag[n];
        map_flag[n]=Fibonacci(n-1)+Fibonacci(n-2);
            
        return map_flag[n];
    }
};