题目难度：中等
考察内容：递推，dp，记忆化搜索
题目内容：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
题目分析：
题目问跳到n一共有多少种跳法，考虑n可以从哪跳上来，从n-1跳一步,从n-2跳两步，所以f[n]=f[n-1]+f[n-2]，这时候发现这和斐波那契数列递推表达式完全一样，斐波那契
不同点在与斐波那契f[0]=0,f[1]=1，而这题没有给出，但是我们可以求出来，f[1]=1,f[2]=2,因为到第一个台阶只有1种跳法， 跳到第二个台阶有两种跳法，这时候递推即可。
思考
通过这题的解法，我们应该思考到dp问题的解法一般怎么解，首先找到递推表达式，也叫做状态转移方程。
其次应该找到起点（我自己起的名字）如同递归的终止条件一样，实际上dp的记忆化搜索解法本质上也是递归，所以也需要一个终止条件。
下面给出三种解法
算法1（递归）
代码如下

class Solution {
public:
    int Fibonacci(int n) {
        if(n==2)return 2;//f[2]=2
        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==1)return 1;//f[1]=1
        if(n==2)return 2;//f[2]=2
        //终止条件
          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=2,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)