方法一

递归
已知斐波那契数列的公式为f(n)=f(n-1)+f(n-2)。要求f(n)就需要知道f(n-1)和f(n-2)，而求f(n-1)需要f(n-2)和f(n-3)，依次推导，直到题目给出的边界{f(0)=0,f(1)=1}。
图解如下：

具体代码如下：

class Solution {
public:
    int Fibonacci(int n) {
        if (n==0 || n==1) return n;//边界条件。
        return Fibonacci(n-1)+Fibonacci(n-2);//递归步骤。
    }
};

时间复杂度：O(2^N)。可以看到，f(n)对应的结点总数为2^(n-2)+1，所以得到时间复杂度为O(2^N)。
空间复杂度：递归栈的空间。

方法二

可以发现方法一中f(n-2)，f(n-3)等等都出现了重复计算的情况，如图所示。

所以可以使用一个数组将其记录下来，在下一次遇到时直接调用，不需要重复计算。
代码如下：

class Solution {
public:
    int fb(int n, vector<int>& f){
        if (n==0 || n==1) return n;//边界条件。
        if (f[n] != -1) return f[n];//计算过的f[n]直接调用。
        return f[n] = fb(n-1, f) + fb(n-2, f);
    }

    int Fibonacci(int n) {
        vector<int> f(41,-1);
        return fb(n, f);
    }
};

时间复杂度：O(N)。每一个f(i)只要计算一次，且计算过程是O(1)的。
空间复杂度：O(N)加递归栈的空间。

方法三

递推
与递归的思路相反，在已知f(0)和f(1)的情况下，我们可以计算出f(2)；在已知f(1)和f(2)的情况下，我们可以计算出f(3)；以此类推，已知f(n-2)和f(n-1)的情况下，我们可以计算出f(n)。
示意图如下：

具体代码如下：

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

        vector<int> f(41,0);//存储计算过的f(i)。
        f[1] = 1;
        for (int i=2;i<=n;i++){
            f[i] = f[i-1]+f[i-2];
        }
        return f[n];
    }
};

时间复杂度：O(N)。递推过程只有一个for循环。
空间复杂度：O(N)。用了一个数组存储斐波那契数列各项。

方法四

可以看到方法三中，每一个f(i)只参加了2次加法运算，之后便不再被使用。于是我们可以使用两个变量a，b而非数组，来记录当前循环需要的两个数列项，并在循环过程中对变量进行更新，用新值覆盖旧值。
具体代码如下：

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

        int a=0,b=1,c=0;//a和b存储前两个斐波那契数列项的值，c存储了当前数列项的值。
        for (int i=2;i<=n;i++){
            c = a + b;
            a = b;//更新a和b的值。
            b = c;
        }
        return c;
    }
};

时间复杂度：O(N)。
空间复杂度：O(1)。