剑指 offer：8、跳台阶

8. 跳台阶

题目描述

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

解题思路：

利用递归思想：可以根据第一步的走法，将所有走法分为两类，第一类是第一步走1个台阶，另一类是第一步走2个台阶，所以n个台阶的走法就等于先走1个台阶后n-1个台阶的走法，加上先走2个台阶后n-2个台阶的走法，用公式表示为：

f(n) = f(n-1) + f(n-2)

有了递归公式，接下来就需要确定终止条件了，当有1个台阶时，只有一种走法，f(1) = 1，当有2个台阶时，有两种走法，f(2) = 2，因此递归公式为：

f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

通过观察递归公式可以发现，递归公式和斐波那契数列相似，则可以改进代码，提高算法运行效率

解答：

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

// 解法2:
class Solution {
public:
    int jumpFloor(int number) {
        int first = 1, second = 1, third = 0;
        if(number == 0)
            return 0;
        if(number == 1)
            return 1;
        for(int i = 1; i < number; ++i)
        {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }
};

大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！

图片来自必应壁纸