每日一题——跳台阶

题目

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

数据范围：1≤n≤40

要求：时间复杂度：O(n) ，空间复杂度： O(1)

示例1

输入：
2
返回值：
2
说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2。

示例2

输入：
7
返回值：
21

思路

一只青蛙一次可以跳1阶或2阶，直到跳到第n阶，也可以看成这只青蛙从n阶往下跳，到0阶，按照原路返回的话，两种方法事实上可以的跳法是一样的——即怎么来的，怎么回去！ 当青蛙在第n阶往下跳，它可以选择跳1阶到n−1，也可以选择跳2阶到n−2，即它后续的跳法变成了f(n−1)+f(n−2)，这就变成了斐波那契数列。

解答代码

class Solution {
public:
    /**
     * @param number int整型 
     * @return int整型
     */
    int jumpFloor(int number) {
        // write code here
        if (number == 1 || number == 2) {
            return number;
        }
        int ret = 0;
        int a = 1;
        int b = 2;
        for (int i = 3; i <= number; i++) {
            ret = a + b;
            a = b;
            b = ret;
        }
        return ret;
    }
};