题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
数据范围：1≤n≤40
要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1)

题解思路：

该题是典型的斐波那契数列
当n = 1时候，f(1) = 1;
当n = 2时候，f(2) = 2;
当n>2时，f(n) = f(n-1) + f(n-2);

图示来自某位大佬，在此借鉴

题解1：递归-效率较低

代码

class Solution {
public:
    int jumpFloor(int number) {
//         当n = 1时候，f(1) = 1;
//         当n = 2时候，f(2) = 2;
//         当n>2时，f(n) = f(n-1) + f(n-2);
        //题解1：递归，效率较低
        if( 1 == number)
            return 1;
        if(2 == number)
            return 2;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

题解2：动态规划-使用数组
注意事项：

1. 创建数组时候同时指定了数组大小和内容，如 vector<int> v(number,0),这样就不能使用push_back后插入方法，因为数组大小已经定了，而push_back是插入在数组后面，所以无法插入。

2. 创建数组时候同时未指定了数组大小和内容，如 vector<int> v，就可以使用push_back方法，注意：若没有开辟数组的空间，不能使用v[1]这种形式。

代码

class Solution {
public:
    int jumpFloor(int number) {
        //题解2：动态规划
        //使用数组方式
        vector<int> v(number,0);//提前创建数组大小和内容
        if(number <=2) return number;
        v[0] = 1;//注意，强调：这里不能用push_back,
        v[1] = 2;//push_back是在数组后面插入，由于数组大小一定，就插入不进去了
        for(int i =2;i< number;i++){
            v[i] = v[i-1] + v[i-2];
        }
        return v[number-1];
    }
};

题解3：动态规划-使用临时变量

代码

class Solution {
public:
    int jumpFloor(int number) {
//         当n = 1时候，f(1) = 1;
//         当n = 2时候，f(2) = 2;
//         当n>2时，f(n) = f(n-1) + f(n-2);
        //题解3：动态规划，使用临时变量
        int a = 1;
        int b = 2;
        if(number == 1) return a;
        if(number == 2) return b;
        int sum = 0;
        for(int i =2;i<number;i++){
            sum = b+a;
            a = b; 
            b = sum;
        }
        return sum;
    }
};