题意

有$nn$个台阶，每次可以跳一级或者两级，求不同的跳跃路线数量。

思路

不难发现，当有$nn$个台阶时，有两种方法：

1. 跳跃1步，剩余$n-1n-1$步
2. 跳跃2步，剩余$n-2n-2$步

因此这一题可以使用递归解决，要算出有$nn$个台阶的方案个数，只需要算出有$n-1n-1$和$n-2n-2$个台阶时的方案并相加就可以了，代码如下。

class Solution {
public:
    int jumpFloor(int number) {
        if(number==1 || number==0) return 1;//边界条件
        return jumpFloor(number-1)+jumpFloor(number-2);//计算方案数
    }
};

复杂度分析

时间复杂度:$O(2^n)O(2^n)$，为递归所需时间。

空间复杂度:$O(2^n)O(2^n)$，是栈空间所用。

改进

上面的代码虽然可以通过题目，但是并未达到题目所要求的的复杂度，经过观察之后我们可以发现，复杂度过高的原因在于对相同台阶的方案多次求解，我们可以添加一个辅助数字进行记忆化搜索，这样可以有效减少重复搜索次数，保证每个台阶数只搜索一次，代码如下。

class Solution {
public:
    int dp[100]={1,1};
    int jumpFloor(int number) {
        if(dp[number]) return dp[number];//若已经搜索过直接返回
        return dp[number]=jumpFloor(number-1)+jumpFloor(number-2);//计算方案数并将其存贮在dp中
    }
};

同时我们发现，题目中只要求求出n级台阶时的方案种数，因此我们可以改为从下而上递推，使用循环变量，进一步减少空间消耗。

class Solution {
public:
    int jumpFloor(int number) {
        if(number==1 || number==0) return 1;//边界
        int a=1,b=1,c=0;
      	for(int i=2;i<=number;i++)
        {
          c=a+b;
          a=b;
          b=c;
        }//循环计算第i，i-1，i-2项
      return c;
    }
};

由此，我们达到了题给复杂度要求。

复杂度分析

时间复杂度:$O(n)O(n)$，每个台阶数只计算了一次。

空间复杂度:$O(1)O(1)$，只使用了常数空间。