10剑指OFFER之跳台阶

参考资料：

无

思路：

斐波那契数列

自己的解法：

class Solution {
public:
    int jumpFloor(int number) {
        if(number<=2)
            return number;
        
        return FibinacciCore(number);
        
    }
    
    int FibinacciCore(int number)
    {
        //从3开始
        int a[256]={0};//全部初始化为0
        a[0] = 0;//跳一级台阶有0种，以下都是
        a[1] = 1;
        a[2] = 2;
        //从头到尾加起来
        for(int i=3;i<=number;i++)
        {
            a[i]=a[i-2]+a[i-1];
        }
        
        return a[number];
    }
    
};
//青蛙跳1级有有1种跳法
//跳2级有2中跳法
//跳3级有3种跳法
//跳4级有5种跳法
//而这就是斐波那契数列

标准答案：

class Solution {
public:
    int jumpFloor(int number) {
        int Result[3] ={0,1,2};
        if(number<=2)
            return Result[number];
        int FiResult = 0;
        int FiOne = 1;
        int FiTwo = 2;
        //利用数学归纳得出是斐波那契数列,从头到尾
        for(int i =3;i<=number;i++)
        {
            FiResult = FiOne+FiTwo;
            FiOne = FiTwo;
            FiTwo = FiResult;
        }
        
        return FiResult;
    }
};