题目描述

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

初始代码

class Solution {
public:
    int jumpFloor(int number) {

    }
};

解题思路

解答本题, 首先要确定采用什么方式. 青蛙每次只能跳1级或2级台阶, 从起始位置开始, 经过若干次跳跃, 它要能够达到第number级台阶.
首先, 我们不去纠结于其中中每一次跳跃, 我们关注最后一次跳跃.

• 如果最后一次跳跃, 跳了两级, 那么说明该次跳跃之前青蛙已经处于第number-2级台阶上;
• 如果最后一次跳跃, 跳了一级, 那么说明该次跳跃之前青蛙已经处于第number-1级台阶上;

由此, 我们将问题拆解为: 青蛙要跳到第number-2级台阶, 有多少种跳法? 以及, 青蛙要跳到第number-1级台阶, 又有多少种跳法?

将我们想要青蛙最终跳到的台阶级数记为n, 函数f(n)返回青蛙跳到第n级台阶能够采取的不同跳法的总数. 那么, 由上述分析, 可以得到递推式:
f(n) = f(n-1) + f(n-2).

可以发现, 这个递推式其实和斐波那契数列的递推式是一样的. 使用递归来实现的话, 它的递归出口是: f(1) = 1和f(2) = 2.

可以参考[剑指OFFER] JZ7 斐波那契数列 的文章, 其中给出了求斐波那契数列的第n个数的多种方法.

下面是本题提交的两份代码, 分别使用了递归和动态规划的思想.

• 递归解法, 自顶向下

class Solution {
public:
    int jumpFloor(int number) {
        if(number <= 2) return number;
        return jumpFloor(number-1) + jumpFloor(number-2);
    }
};

• 动态规划解法, 自底向上

class Solution {
public:
    int jumpFloor(int number) {
        if(number<=2) return number;
        int a=1, b=2, i;
        for(i=3; i<=number; i++)
        {
            b = a + b;
            a = b - a;
        }
        return b;
    }
};