思路: 题目分析: 一只青蛙一次可以跳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),建立了一个数组