青蛙跳台阶是很经典的一道题目了，一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。题目要求：需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

利用递归的思路，青蛙每次跳一级或者两级，因此每次jump(n)函数都会调用jump(n-1)和jump(n-2)，而当n为零的时候，就说明青蛙已经跳上目标的台阶了，由于每次做出的选择都不会重复，因此每当有一个jump函数的输入为0时，就说明有一种跳法。
代码如下：

class Solution {
public:
    int sum=0;
    //jump函数，模拟青蛙目前所处的状态和青蛙下一次跳了之后的状态
    void jump(int n){
       //n小于零说明跳过了，属于非法情况应该终止
        if(n<0)return;
        //n为0说明青蛙跳上了目标台阶，方案树加一
        if(n==0)
            sum=(++sum)%1000000007;
        else{
            jump(n-1);
            jump(n-2);
        }
    }
    int numWays(int n) {
       jump(n);
       return sum;
    }
};

利用递归算法，其调用了一个二叉树形的函数调用结构，因此其时间复杂度为O(2^n)，是开销非常大的算法，那有没有什么办法可以降低时间复杂度呢。

再来回顾题目，我们发现第n阶台阶仅可能是从第n-1阶台阶或者第n-2阶台阶跳上来的，因此第n阶台阶的方案数等于第n-1阶台阶和第n-2阶台阶的方案之和。

class Solution {
public:
    int numWays(int n) {
        int sum=0,a=1,b=2;
        //直接输出目标台阶为0级、1级、2级的情况
        if(n==0||n==1)
            return 1;
        else if(n==2)
            return 2;
        else
            for(int i=3;i<=n;i++){
            //a为i-2级台阶方案数，b为i-1级台阶方案数，每次i加1后利用“第n阶台阶的方案数等于第n-1阶台阶和第n-2阶台阶的方案之和”规律对a、b的值进行更新
                int temp=a;
                a=b;
                b=(b+temp)%1000000007;                
            }
        return b;
    }
};

这样题目的时间复杂度就被降低为O(n)。