题目的主要信息：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

方法一：

采用递归。如果跳上0级或1级台阶只有一种跳法。否则采用递归，每次可以跳1级或者跳2级，所以总跳法等于先跳一步的跳法加上先跳两步的跳法。

具体做法：

class Solution {
public:
    int jumpFloor(int number) {
        if(number == 0 || number == 1) return 1;//如果是一级台阶或两级台阶只需跳一步
        return jumpFloor(number-1) + jumpFloor(number-2);//跳一级或者跳两级
    }
};

复杂度分析：

时间复杂度： $O (n)$ ,如果每次只跳一级，最多需要递归n次。
空间复杂度： $O (n)$ ，递归栈大小为n。

方法二：

动态规划。arr[i]表示跳上第i级台阶有arr[i]种跳法。每次可以跳一级或者两级，所以跳上第i级台阶可以是从第i-1级台阶跳一步来的，也可以是从第i-2级台阶跳两步来的，因此arr[i]=arr[i-1]+arr[i-1]。更新完整个动态数组后，arr[number]即为跳上number级台阶的跳法。 alt 具体做法：

class Solution {
public:
    int jumpFloor(int number) {
        vector<int> arr(number+1,1);
        for(int i = 2; i <= number; i++){//更新动态数组
            arr[i] = arr[i-1] + arr[i-2];//跳一步的跳法加跳两步的跳法
        }
        return arr[number];
    }
};

复杂度分析：

时间复杂度： $O (n)$ ,需要遍历一遍动态数组。
空间复杂度： $O (n)$ ，动态数组大小为n。

题解 | #跳台阶#

题目的主要信息：

方法一：

方法二：