一、题目描述

JZ9跳台阶扩展问题
本题有一个简单版本,建议先做一下题目链接
题目大意：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
注意审题：每一种跳法都是顺序相关的,即先跳一步再跳两步不等价于先跳两步再跳一步

二、算法1（递归）

算法思路

1.解题思路：暴力尝试每一种走法,到达终点后记为一种方案
2.实现方式：递归时我们需要知道当前处于第几级台阶,以及目标是到达第几级台阶,因此递归函数接受两个参数,一个是当前所在的位置,一个是目标位置,递归边界即当前所在位置为目标位置时结束,每个阶段尝试不同的步数即可.
3.这种解法的时间复杂度过高,因此不建议采用

代码实现（C++11）

class Solution {
public:
    int jumpFloorII(int number) {
        return dfs(0, number);
    }

    int dfs(int cur, int target){
        if(cur == target) return 1;
        int tot = 0;
        for(int i = 1; cur + i <= target; i++)
            tot += dfs(cur + i, target);
        return tot;
    }
};

时间复杂度：O(n^n)
空间复杂度：O(n^n)

时间复杂度优化（记忆化搜索）

1.对于递归求方案数的问题,我们可以自然的联想到用记忆化搜索来进行时间优化,因为在递归的过程中可能会出现大量相同的分支,所以我们可以使用一个备忘录数组记录已知的分支,当遇到重复子问题时,直接返回备忘录记下的结果即可
2.根据递归的参数,我们可以想到一种定义备忘录数组的方式,即memo[i]表示从第i级台阶走到终点的方案数
3.实现方式：一般来说,我们习惯将memo数组初始化为-1,表示还未求得方案,因为对于一些问题来说0也是一种合法方案

代码实现（C++11）

class Solution {
public:
    vector<int> memo;

    int jumpFloorII(int number) {
        memo.resize(number + 1, -1);
        return dfs(0, number);
    }

    int dfs(int cur, int target){
        if(memo[cur] != -1) return memo[cur];
        if(cur == target) return 1;
        int s = 0;
        for(int i = 1; cur + i <= target; i++){
            s += dfs(cur + i, target);
            }
        return memo[cur] = s;
    }
};

时间复杂度：平均时间复杂度O(n^2)
空间复杂度：O(n^2)

三、算法2（动态规划）

算法思路

1.解题思路：与跳台阶问题相似,定义f数组,f[i]表示从起点到达第i级台阶的方案数,由于每次跳的步数无限制,因此可以求得状态转移方程：

代码实现（C++11）

class Solution {
public:
    int jumpFloorII(int number) {
        int f[number + 1];
        f[0] = 1;
        f[1] = 1;
        for(int i = 2; i <= number; i++){
            f[i] = 0;
            for(int j = 0; j < i; j++){
                f[i] += f[j];
            }
        }
        return f[number];
    }
};

时间复杂度：O(n^2)
空间复杂度：O(n)

时间复杂度优化（数学）

观察状态转移方程,我们可以看出F(x - 1) = F(0) + F(1) + ... + F(x - 2),这与F(x)的方程有了重复的部分,替换可得F(x) = 2 * F(x - 1) (x > 1)
F(0) = 1
F(1) = 1
F(2) = 2
F(3) = 4
...
F(n) = 2 * F(n - 1)
可见从F(1)开始满足F(i) = 2^(i - 1)
故可以可以快速幂算法将时间复杂度优化至O(logn)级别

代码实现（C++11）

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0) return 1;
        return qmi(2, number - 1);
    }

    int qmi(int a, int b){
        int res = 1;
        while(b){
            if(b & 1) res *= a;
            a *= a;
            b >>= 1;
            }
        return res;
    }
};

时间复杂度：O(logn)
空间复杂度：O(1)