#每日一题 剑指offer 青蛙跳台阶问题

青蛙跳台阶是很经典的一道题目了，一只青蛙一次可以跳上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;elsefor(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)。