题目的主要信息：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

方法一：

采用递归。如果跳上0级或1级台阶只有一种跳法。否则采用递归，每次可以跳1级或者跳2级、3级……n级，所以总跳法等于所有可能的跳法之和。

具体做法：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0 || number == 1) return 1;//如果是一级台阶或两级台阶只需跳一步
        int count = 0;
        for(int i=1;i<=number;i++){
            count += jumpFloorII(number-i);//递归
        }
        return count;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，for循环嵌套递归。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

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

class Solution {
public:
    int jumpFloorII(int number) {
        vector<int> arr(number+1,1);
        for(int i = 2; i <= number; i++){//更新动态数组
            int count = 0;
            for(int j = 1; j <= i; j++){//遍历一遍所有可能的跳法
                count += arr[i-j];
            }
            arr[i] = count;
        }
        return arr[number];
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，双层for循环。
• 空间复杂度：$O(n)O(n)$，数组arr的大小为n。

方法三：

找规律。

f[n] = f[n-1] + f[n-2] + ... + f[0]

f[n-1] = f[n-2] + f[n-3] + ... + f[0]

化简得到f[n] = 2*f[n-1]。初始条件f[0] = f[1] = 1，所以f[n] = 2^(n-1)

具体做法

class Solution {
public:
    int jumpFloorII(int n) {
         if (n == 0 || n == 1) return 1;//直得出
         return 1<<(n-1);//2^(n-1)
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，进行移位操作。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。