一、题目描述

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

二、算法1 (递归）

算法思路

1.总体思路：暴力尝试所有的走法
2.递归边界即当目前处于第n个台阶时结束

代码实现 （C++11）

class Solution {
public:
    int jumpFloor(int number) {
        int ans = dfs(0, number);
        return ans;
    }

    int dfs(int start, int end){
        if(start == end) return 1;
        if(start > end) return 0;    // 超过end不合法
        return dfs(start + 1, end) + dfs(start + 2, end);
    }
};

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

三、算法2 （动态规划）

使用动态规划算法,我们可以定义f数组,f[i]表示从起点跳到第i级台阶总共有多少种跳法,当我们处于第i级台阶时,可以知道上次可以是从第i - 1级台阶跳过来,也可以从第i - 2级台阶跳过来,结合f数组的含义,我们可以得到状态转移方程为:

代码实现 （C++11）

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

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

空间优化

由于F(x)，实际上我们不需要将0~n的所有状态记录下来,而只需要知道F(x - 1)和F(x - 2)的值即可，因此可以用两个变量来表示，递推即可

class Solution {
public:
    int jumpFloor(int number) {
        if(number == 0 || number == 1) return 1;
        int pre = 1, cur = 1;
        for(int i = 2; i <= number; i++){
            int tmp = pre + cur;
            pre = cur;
            cur = tmp;
        }
        return cur;
    }
};

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

算法3 （矩阵快速幂）

观察递推式我们可以发现,它的本质其实就是斐波那契数列,因此可以采用和其相同的方法解决本题,矩阵快速幂解法参见斐波那契数列题解

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