08.跳台阶.md

8.跳台阶

题目描述

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

解题思路

• 这个要反向思维来想，由于只能跳1级或者跳2级，因此跳到第n级台阶时，最后一跳只有两种可能，一种是从前一级台阶跳1级，另一种是从前两级台阶跳2级，得出f(n) = f(n-1) + f(n-2)，可知用斐波那契数列的方法即可。
• 还有一种理解方式是，第一次跳有两种方法，一种是跳1级，一种是跳2级，如果跳1级的话就还剩下n-1级，如果跳2级的话就还剩下n-2级，把第一次跳完以后的位置当成起点的话，后面的问题就相当于跳上第n-1级和跳上第n-2级台阶有多少种方法，也能得出f(n) = f(n-1) + f(n-2)。
• 用数学归纳法也能逐渐找到该规律
• 和斐波那契数列一样，递归效率很低，因此不用递归

C++代码

• 普通方法

class Solution {
public:
    int jumpFloor(int number) {
        if(number<1){
            throw "number must >0";
        }
        else if(number == 1){
            return 1;
        }
        else if(number == 2){
            return 2;
        }
        else{
            int a=1, b=2, temp=0, i=2;
            while(i<number){
                temp = a + b;
                a = b;
                b = temp;
                i++;
            }
            return b;
        }
    }
};

• 骚操作

//其实也是不停地算出下一个值的过程，只不过不容易想到，
//效率和上面的差不多，只不过代码简洁得多
class Solution {
public:
    int jumpFloor(int number) {
        int a = 1, b = 1;
        while(--number){
            b += a;
            a = b - a;
        }
        return b;
    }
};