题解 | #跳台阶扩展问题#

题解一：递归
题解思路：考虑最后一步是跳几阶到达目标位置的。
主要分析：
1.令f(n)表示n阶台阶总的跳法
2.假设最后只跳一步，那么f(n) = f(n-1); 最后跳两步，那么f(n) = f(n-2)；以此类推，可知总的跳法为f(n) = f(n-1) + f(n-2) +....+f(0)
图示：

复杂度分析：
时间复杂度：O(N^N)
空间复杂度：O(N) : 递归栈深度
实现如下:

class Solution {
public:
    int jumpFloorII(int number) {
        int ans = 1;
        for(int i = 1; i<number;i++)
            ans += jumpFloorII(number-i);  //计算f(number-1)
        return ans;
    }
};

题解二：记忆化优化递归
解题思路：与递归思路一样，但是普通的递归进行了多次无用计算。 比如在上述递归中，f(1),f(2).....被多次计算。我们可以使用记忆化来优化复杂度。
复杂度分析：
时间复杂度：O(N)，从1~n依次遍历了台阶数
空间复杂度：O(N)，利用一个标记数组f，记录以往被运算过的台阶的跳法；

实现如下:

class Solution {
public:
    int f[10001]{0};        //记录
    int jumpFloorII(int number) {
        if(number==0) return 1;  //边界
        if(f[number]) return f[number];  //如果f[nummber]之前已经计算过，那么直接返回
        //f[number] 没有计算过，f[number] = f[number-1] +.....+f[0]
        for(int i = 0 ;i<number;i++)
            f[number] += jumpFloorII(i);
        return f[number];
    }
};

题解三： 动态规划+
题解思路：延续题解一中的公式f(n) = f(n-1) + f(n-2) +....+f(0)
分析：
1.知道f(n) = f(n-1) + f(n-2) +....+f(0)，那么f(n-1) = f(n-2) + f(n-3) +......+f(0);
2.可知 f(n) = 2 * f(n-1);
3.初始ans = 1;
复杂度分析：
时间复杂度：O(N)，从1~n依次遍历了台阶数
空间复杂度：O(1)，没有申请其他空间存放数据

实现如下:

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==1||number==0) return 1;
        int ans = 1;
        for( int i = 2; i<=number;i++)
            ans *= 2;
        return ans;
    }
};

题解四： 数学
解题思路： 从题解三得出的公式，继续优化复杂度
分析：
f(1) = 1;
f(2) = 2 * f(1) = 2^1
f(3) = 2 * f(2) = 4 = 2^2
假设f(k) = 2^(k-1) 成立
那么 f(k+1) = 2 * f(k) = 2^(k);
得出 f(n) = 2^(n-1);
复杂度分析:
时间复杂度：O(1)，一次位运算
空间复杂度：O(1)，没有使用其他空间
实现如下：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==1||number==0) return 1;
        return 1<<number-1;
    }
};