题目难度：入门
考察内容：递推，dp
题目内容：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
题目分析
首先我们都知道斐波那契数列的递推式子为f[i]=f[i-1]+f[i-2],我们要知道f[n]就要知道f[n-1],f[n-2]，要是到f[n-1]就要知道f[n-2],f[n-3]。。。很明显这可以用递归来解决，递归的终止条件就是我们知道的f[0]=0,f[1]=1
于是我们有了一种解法
算法1（递归）
代码如下

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0)return 0;//f[0]=0
        if(n==1)return 1;//f[1]=1
        //终止条件
          return Fibonacci(n-1)+Fibonacci(n-2);//f[n]=f[n-1]+f[n-2]
    }
};

复杂度分析：时间复杂度，每次调用f[n-1],f[n-2]所以时间复杂度为O(2^n)
空间复杂度，没有额外空间，空间复杂度O(1)
可以发现时间复杂度太高
算法2（记忆化搜索）
可以发现有很多值是重复调用的，浪费了大量时间,可以记录每次的值，下次再碰到可以直接O(1)查询
代码如下

class Solution {
public:

    int f[40]={0};
    int Fibonacci(int n) {
        if(f[n])return f[n];
        //如果f[n]已经求出了，直接调用即可
        if(n==0)return 0;//f[0]=0
        if(n==1)return 1;//f[1]=1
        //终止条件
          f[n]=Fibonacci(n-1)+Fibonacci(n-2);//f[n]=f[n-1]+f[n-2]
        return f[n];
    }
};

复杂度分析：时间复杂度，f[i]只会搜索一次，所以时间复杂度为O(n)
空间复杂度，有额外空间记录f[i]，空间复杂度O(n)
空间复杂度达到了O(n)
继续优化
算法3(递推)
反向考虑，我们知道了f0,f1,所以f2=f0+f1,我们知道了f2,所以f3=f2+f1。。。发现可以直接递推，但是空间复杂度还是O(n)的，每次只用到了两个变量fi-1,fi-2，所以可以只设置两个变量a,b,ans=a+b,然后递推，a=b,b=ans.
代码如下

class Solution {
public:
    int Fibonacci(int n) {
            long long a=1,b=1,ans=1;
            //a表示f[i-2],b表示f[i-1]
        if(n==0)return 0;
            //特判0
        for(int i=3;i<=n;i++)
            ans=a+b,a=b,b=ans;
            //f[n]=a+b,f[i-2]=b,f[i-1]=ans
        return ans;
    }
};
**复杂度分析：**时间复杂度，f[i]只会搜索一次，所以时间复杂度为O(n)
             **空间复杂度**，没有额外空间，空间复杂度O(1)