题解 | #跳台阶#

学习记录，有些的不对的地方，欢迎指正！

//------法1：-----递归-------------会超时----
class Solution {
public:
    int jumpFloor(int number) {
        if(number<=2) return number;//错误，如果number为0，实际应该返回1
        if(number<=1) return 1;//正确
        return jumpFloor(number-1)+jumpFloor(number-2);

    }
};

//------法2：-----记忆化搜索--------不会超时----
//记忆化搜索
class Solution {
public:
    int fin(int n,vector<int>&dp){
        if(n<=2) return n;//错误  n=0 输出也是1，除非题目说是0
        if(n<=1) return 1;//正确
        if(dp[n]!=-1) return dp[n];
        return dp[n]=fin(n-1,dp)+fin(n-2,dp);
    }
    int jumpFloor(int number) {
        //记忆化搜索
        vector<int>dp(number+1,-1);
        return fin(number,dp);

    }
};
//------法3：-----dp/迭代-------------
//-----dpok--------
class Solution {
public:
    int jumpFloor(int number) {
        if(number<=1) return 1;//记得判空，如果为空，那么下面的dp[1]就是错误的
        vector<int>dp(number+1);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=number;++i){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[number];

    }
};
//-----------迭代-----------------ok---空间优化-
class Solution {
public:

    int jumpFloor(int number) {
        int num1=1;
        int num2=1;
        int num=1;
//         斐波那契数列
        for(int i=2;i<=number;++i){
            num=num1+num2;
            num1=num2;
            num2=num;
        }
        return num;

    }
};