题目描述

跳台阶

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

分析

根据题意，青蛙一次可以跳1级台阶，2级台阶，那么要跳到n级有两种情况：
1.先跳到n-1级，最后一步跳上1级到n级。
2.先跳到n-2级，最后一步跳上2级到n级。
假设跳到n级有F(n)种方法，那么根据上面分析可知F(n) = F(n-1)+F(n-2).其中F(1) = 1,F(2) = 2。
类似于斐波那契数列的分析，有递归方法和递推方法。

源码

递归方法

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

递推方法

//利用递推
class Solution {
public:
    int jumpFloor(int number) {
        if(number == 1) return 1;
        if(number == 2) return 2;
        if(number >2){
            int  a1,a2,res;
            a1= 2;
            a2= 1;
            for(int i = 3;i<=number;i++)
            {
                res = a1+a2;
                a2 = a1 ;
                a1 = res;
             }
            return res;
        }
    }
};