剑指offer-JZ8

C++
本题是斐波那契数列的变种；
第n级台阶有两种跳法： 从n-1级跳1级 + 从n-2级跳2级；
因此 f[n]=f[n-1] + f[n-2];
推知：
n=0-------1
n=1-------1
n=2-------f[0]+f[1]=2;
三种方法：
动态规划、递归、直接数组保存（但这里未说明n范围，担心会超时）---参考JZ7
1动态规划：

class Solution {
public:
    int jumpFloor(int number) {
        int tmp0=1, tmp1=1, ans;
        if (number ==0 || number == 1) return 1;
        for (int i=1; i<number; i++){
            ans = tmp0 + tmp1;
            tmp0 = tmp1;
            tmp1 = ans;
        }
        return ans;
    }
};

2-递归

public:
    int jumpFloor(int number) {
        if (number==0 || number==1) return 1;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

加入优化

class Solution {
public:
    int Fib(int n, vector<int> &dp){
        if (n==0 || n==1) return 1;
        if (dp[n] != -1) return dp[n] ;
        return dp[n]=Fib(n-1, dp) + Fib(n-2,dp);
    }
    int jumpFloor(int number) {
        vector<int> dp(number+1, -1);
        return Fib(number, dp);
    }
};

3-利用数组,这里默认1000，其实是不合理的

class Solution {
public:
    int jumpFloor(int number) {
        int f[1000] = {0};
        f[0]=1;
        f[1]=1;
        for(int i=2; i<number+1; i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[number];
    }
};