题解 | #跳台阶#

题目主要信息：

• 一只青蛙一次可以跳1阶或2阶
• 求跳到第$nn$阶的种类数

举一反三：

学习完本题的思路你可以解决如下题目：

BM62.斐波那契数列

BM64.最小花费爬楼梯

BM69.把数字翻译成字符串

方法一：迭代相加（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。本解法属于动态规划空间优化方法

思路：

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

具体做法：

• step 1：低于2项的数列，直接返回n。
• step 2：初始化第0项，与第1项分别为0，1.
• step 3：从第2项开始，逐渐按照公式累加，并更新相加数始终为下一项的前两项。

图示：

Java实现代码：

public class Solution {
    public int jumpFloor(int target) {
        //从0开始，第0项是0，第一项是1
        if(target <= 1)   
            return 1;
        int res = 0;
        int a = 0;
        int b = 1;
        //因n=2时也为1，初始化的时候把a=0，b=1
        for(int i = 2; i <= target; i++){
        //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
            res = (a + b);
            a = b;
            b = res;
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int jumpFloor(int number) {
        //从0开始，第0项是0，第一项是1
        if(number <= 1)    
            return 1;
        int res = 0;
        int a = 0;
        int b = 1;
        //因n=2时也为1，初始化的时候把a=0，b=1
        for(int i = 2; i <= number; i++){
        //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
            res = (a + b);
            a = b;
            b = res;
        }
        return res;
    }
};

Python代码实现：

class Solution:
    def jumpFloor(self , number: int) -> int:
        #从0开始，第0项是1，第一项是1
        if n <= 1:    
            return 1
        res = 0
        a = 1
        b = 1
        #初始化的时候把a=1，b=1
        for i in range(2, n + 1): 
        #第三项开始是前两项的和,然后保留最新的两项，更新数据相加
            res = (a + b)
            a = b
            b = res
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为输入的数
• 空间复杂度：$O(1)O(1)$，常数级变量，没有其他额外辅助空间

方法二：递归法（扩展思路）

知识点：递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

思路：

我们也可以根据公式倒推，因为$F(n)=F(n-1)+F(n-2)F(n)=F(n-1)+F(n-2)$，而$F(n-1)F(n-1)$与$F(n-2)F(n-2)$又可以作为子问题继续计算，因此可以使用递归。

• 终止条件： 当递归到数列第1项或是第0项的时候，可以直接返回数字。
• 返回值： 返回这一级子问题的数列值。
• 本级任务： 获取本级数列值：即前两项相加。

具体做法：

• step 1：低于2项的数列，直接返回1。
• step 2：对于当前n，递归调用函数计算两个子问题相加。

Java实现代码：

public class Solution {
    public int jumpFloor(int target) {
        //这里第0项为1，第1项为1
        if(target <= 1)
            return 1;
        else
            //递归子问题相加
            return jumpFloor(target - 1) + jumpFloor(target - 2); 
    }
}

C++实现代码：

class Solution {
public:
    int jumpFloor(int number) {
        //这里第0项为1，第1项为1
        if(number <= 1)
            return 1;
        else
            //递归子问题相加
            return jumpFloor(number - 1) + jumpFloor(number - 2);  
    }
};

Python代码实现：(Python版本不能完全通过，改进见方法三)

class Solution:
    def jumpFloor(self , number: int) -> int:
        #从0开始，第0项是1，第一项是1
        if number <= 1:    
            return 1 
        #根据公式递归调用函数
        return self.jumpFloor(number - 1) + self.jumpFloor(number - 2) 

复杂度分析：

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

方法三：递归改进（扩展思路）

思路：

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

具体做法：

• step 1：使用dp数组记录前面的数列值。
• step 2：函数中低于2项的数列，直接返回1。
• step 3：对于当前n，如果dp数组中存在则直接使用，否则递归调用函数计算两个子问题相加。

图示：

Java实现代码：

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

C++实现代码：

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

Python代码实现：

class Solution:
    def __init__(self):
        self.num = [0 for i in range(41)]
    def jumpFloor(self , number: int) -> int:
        #从0开始，第0项是1，第一项是1
        if number <= 1:    
            self.num[number] = 1
            return 1
        #若是dp中有值则不需要重新递归加一次
        if self.num[number - 1] == 0:
            self.num[number - 1] = self.jumpFloor(number - 1)
        if self.num[number - 2] == 0:
            self.num[number - 2] = self.jumpFloor(number - 2)
        #根据公式相加
        return self.num[number - 1] + self.num[number - 2] 

复杂度分析：

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

方法四：动态规划（扩展思路）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

既然与斐波那契数列相同，我们就把它放入数组中来解决。

具体做法：

• step 1：创建一个长度为$n+1n+1$的数组，因为只有$n+1n+1$才能有下标第$nn$项，我们用它记录前$nn$项斐波那契数列。
• step 2：根据公式，初始化第0项和第1项。
• step 3：遍历数组，依照公式某一项等于前两项之和，将数组后续元素补齐，即可得到$fib[n]fib[n]$。

Java实现代码：

public class Solution {
    public int jumpFloor(int target) {
        //从0开始，第0项是1，第一项是1
        if (target <= 1)    
             return 1;
        int[] temp = new int[target + 1];
        //初始化
        temp[0] = 1;
        temp[1] = 1;
        //遍历相加
        for (int i = 2; i <= target; i++) 
            temp[i] = temp[i - 1] + temp[i - 2];
        return temp[target];
    }
}

C++实现代码：

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

Python代码实现：

class Solution:
    def jumpFloor(self , number: int) -> int:
        #从0开始，第0项是1，第一项是1
        if number <= 1:    
            return 1
        temp = [0 for i in range(number + 1)]
        #初始化
        temp[0] = 1
        temp[1] = 1
        #依次相加
        for i in range(2, number + 1): 
            temp[i] = temp[i - 1] + temp[i - 2]
        return temp[number]

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历了一次长度为$nn$的数组
• 空间复杂度：$O(n)O(n)$，建立了一个数组辅助