剑指offer8：青蛙跳台阶

1. 题目描述

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

2. 思路和方法

　　青蛙每一次跳跃只有两种选择：一是再跳1级阶梯到达第n级阶梯，此时小青蛙处于第n-1级阶梯；或者再跳2级阶梯到达第n级阶梯，此时小青蛙处于n-2级阶梯。于是，n级阶梯的跳法总是依赖于前n-1级阶梯的跳法总数f(n-1)和前n-2级阶梯的跳法总数f(n-2)。因为只有两种可能性,所以,f(n)=f(n-1)+f(n-2)；

　　递推公式f(n)=f(n-1)+f(n-2)：很熟悉，就是斐波那契数列求和验证一下，青蛙1级有1种跳法，2级有2种跳法，3级有3种跳法，4级有5种跳法。

3. C++核心代码

3.1 递归（效率低，时间复杂度O(n²)）

 1 class Solution {
 2 public:
 3 int jumpFloor(int number) {
 4         if(number==1)
 5             return 1;
 6         else if(number==2)
 7             return 2;
 8         else{
 9             return jumpFloor(number-1)+jumpFloor(number-2);
10         }
11     }
12 };

View Code

3.2 非递归（时间复杂度O(n)）

 1 class Solution {
 2 public:
 3     int jumpFloor(int number) {
 4         if (number < 0)
 5         {
 6             return 0;
 7         }
 8         if (number == 0 || number == 1 || number == 2)
 9         {
10             return number;
11         }
12         int f1 = 1;
13         int f2 = 2;
14         int result = 0;
15         for (int i = 3; i <= number; i++)
16         {
17             result = f1 + f2;
18             f1 = f2;
19             f2 = result;
20         }
21         return result;
22     }
23 };