题解 | #跳台阶#

C++
两种思路：递归和自底向上
（1）递归
首先说我自己是通过归纳总结得出实际上就是从1开始的斐波那契数列的规律，写出了递归的代码。看了别人的思路发现比较好的方式是找寻内在联系。青蛙一次可以跳1阶，也可以跳2阶，那么当青蛙在第n阶的时候，它上一步可以在第n-1阶也可以在第n-2阶，那么假设n阶台阶有F(n)种跳法，那么n-1阶就有F(n-1)阶跳法，同理n-2阶就有F(n-2)种跳法，所以F(n)=F(n-1)+F(n-2)，也就是斐波那契数列的计算方法。代码如下

/**
 * 
 * @param number int整型 
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
    //计算了6阶台阶的情况，发现是斐波那契数列
    if(number<=2)
    {
        return number;
    }
    else
    {
        return jumpFloor(number-1)+jumpFloor(number-2);
    }

}

（2）自底向上
笔试的时候可以采用上面的想法，面试的时候可以采用下面的方式对上面的代码进行优化，降低复杂度。其实原理就是斐波那契数列的计算原理。

(这里可以看https://blog.nowcoder.net/n/ef601ffbb33a42ff963f65364accd5cd?f=comment来理解)

/**
 * 
 * @param number int整型 
 * @return int整型
 */
int jumpFloor(int number ) {
    // write code here
   //考虑优化复杂度
    int a=1,b=1,c=0;//设定c是F(n),a是F(n-2),b是F(n-1)
    if(number==1)
    {
        return 1;
    }
    else
    {
        for(int i=0;i<number-1;i++)
        {
            c=a+b;//F(n)=F(n-2)+F(n-1)
            a=b;//再计算下一项的话就应该是F(n+1)=F(n-1)+F(n)，因此把b赋给a
            b=c;//把c赋给b，再计算a+b即为F(n+1)=F(n-1)+F(n)
        }
        return c;
    }

}