题解 | #跳台阶#

一.题目描述
有n级台阶，青蛙每一次可以跳上去1级台阶或者2级台阶，问有多少种跳法？
二.算法1(利用数组求)
我们可以通过推理来找出。
第3位可以由第1阶台阶跳2阶或第2阶段跳1阶段得出。
第4位可以由第2阶台阶跳2阶或第3阶段跳1阶段得出。
第5位可以由第3阶台阶跳2阶或第4阶段跳1阶段得出。
......
最后可以得出：

其中dp[i]表示跳到第i个台阶的走法

class Solution {
public:
    int jumpFloor(int number) {
        int dp[1005];
        dp[1]=1;//跳台阶为1，2的方案数字 很容易想出来了
        dp[2]=2;
        for(int i=3;i<=number;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[number];
    }
};

复杂度：o(n)
优缺点：性能好，操作也比较j'di
三.算法2(利用递归求)
青蛙跳楼梯，要么一次跳一级，要么一次跳走两级，那青蛙每次的走法就等于=上一次跳的方案数+上上次的方案数
那么结果就很显然了，就是求n项斐波那契数列了，可以利用递归去求解

class Solution {
public:
    int jumpFloor(int number) {
        if(number<=1) return 1;//台阶数为1个的时候 只有一种方案
        else return jumpFloor(number-1)+jumpFloor(number-2);//当台阶数大于1的时候 方案数是上一次跳的方案数加上上上次的方案数
    }
};

复杂度：o(2^n)
优缺点：代码实现简单 但是时间复杂度高