剑指offer-JZ7

c++
考查斐波那契数列的知识，
F[I]=F[I-1]+F[I-2];
F[0]=0; F[1]=1;
因此直接遍历，时间 ,空间 动态规划：

class Solution {
public:
    int Fibonacci(int n) {
        int temp1=0, temp2=1,ans=0;
        if (n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
            for(int i=1; i<n; i++){
                ans = temp1 + temp2;
                temp1 = temp2;
                temp2 = ans;
            } 
            return ans;
        }


    }
};

也可以直接利用数组，因为给定n<39，直接给出。

class Solution {
public:
    int Fibonacci(int n) {
        int f[40]={0};
        f[0]=0;
        f[1]=1;
        for (int i=2; i<40; i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }
};

简化一点的 递归思路，时间 ,空间大：

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

保存结果 + 递归；这样，不需要重复计算。

class Solution {
public:
    int Fib(int n, vector<int> &dp){
         if(n==0 || n==1) return n;
         if (dp[n] != -1) return dp[n];

         return dp[n] = Fib(n-1, dp) + Fib(n-2, dp);
    }
    int Fibonacci(int n) {
       vector<int> dp(45,-1);
        return Fib(n, dp);
    }
};