【剑指offer】08 跳台阶

题目地址：跳台阶

题目描述                                   

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

时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 64M，其他语言128M

题目示例                                   

示例1：

输入：

1

返回值：

1

示例2：

输入：

4

返回值：

5

解法分析                                   

我记得这好像是一道小学奥数题？当有n节台阶时，如果青蛙最后一步跳一节，那么它跳n-1节台阶时有多少种跳法，跳n节台阶时就有多少种跳法；如果青蛙最后一步跳两节，那么它跳n-2节台阶时有多少种跳法，跳n节台阶时就有多少种跳法。可以看出，跳n节台阶的跳法种类，相当于跳n-1节台阶和跳n-2节台阶跳法的和。

熟悉吧？没错，这就是个斐波那契数列。解法自然跟上一题斐波那契数列一致。

代码                                         

数组+循环：

function jumpFloor(number)
{
    // write code here
    if(number<=2){
        return number;
    }else{
        var fib = [];
        fib[1] = 1;
        fib[2] = 2;
        for(var i=3;i<=number;i++){
            fib[i]=fib[i-2]+fib[i-1];
        }
        return fib[number];
    }
}

循环：

function jumpFloor(number)
{
    // write code here
    var res = 1, mid = 2;
    while(--number){
        mid+=res;
        res=mid-res;
    }
    return res;
}

执行结果