题解 | #跳台阶#

思路： 题目分析： 一只青蛙一次可以跳1阶或2阶，直到跳到第n阶，也可以看成这只青蛙从n阶往下跳，到0阶，按照原路返回的话，两种方法事实上可以的跳法是一样的——即怎么来的，怎么回去！ 当青蛙在第n阶往下跳，它可以选择跳1阶到n-1，也可以选择跳2阶到n-2，即它后续的跳法变成了f(n-1)+f(n-2),这就变成了斐波那契数列。因此可以按照斐波那契数列的做法来做：即输入n，输出第n个斐波那契数列的值。

方法一：递归法 根据斐波那契数列的函数，书写递归，需要注意这里第2阶为2，而不是之前斐波那契数列中的1：

class Solution {
public:
    int jumpFloor(int number) {
        if(number <= 1)//不同于斐波那契数列那道题，这里第0项为1，第1项为1，因为实际问题实际考虑
            return 1;
        else
            return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
};

复杂度分析：

• 时间复杂度：O(2^n)，由图可知，每个递归会调用两个递归，因此呈现2的指数增长
• 空间复杂度：O(n), 栈空间最大值

方法二：递归改进 递归虽然简单，但是从上图可以看出，重复计算了很大一部分，可以利用数组记录每个F(n)，需要的时候直接调用数组里面的值即可。

class Solution {
public:
    int dp[50] = {0};//设置全局变量，因为实际问题中没有0，则可用0作初始标识值
    int F(int n){
        if(n <= 1)
            return 1;
        if(dp[n] != 0)   //若是dp中有值则不需要重新递归加一次
            return dp[n];
        return dp[n] = F(n - 1) + F(n - 2);//若是dp中没有值则需要重新递归加一次
    }
    int jumpFloor(int number) {
        return F(number);
    }
};

复杂度分析：

• 时间复杂度：每个数字只算了一次，故为O(n)
• 空间复杂度：O(n)，栈空间最大深度

方法三：动态规划 具体做法：创建一个n+1大小的动态数组temp，初始化第0位为1，第1位为1，然后根据公式相加即可得到后面的，数组最后的下标n即为所求。

class Solution {
public:
    int jumpFloor(int n) {
        if (n <= 1)    //从0开始，第0项是1，第一项是1
             return n;
        int* temp = new int[n+1];
        temp[0] = 1;
        temp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            temp[i] = temp[i-1] + temp[i-2];
        }
        return temp[n];
    }
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)，建立了一个数组