剑指offer-JZ9

c++
考查斐波那契数列的变种，
第n级 = f[n-1]+f[n-2]+......f[0]
三种思路：暴力、递归、 动态规划、
思路一，暴力法：

class Solution {
public:
    int jumpFloorII(int number) {
        if (number ==0 || number==1) return 1;
        vector<int> f(number+1, 0);
        f[0]=1; 
        f[1]=1;
        for (int i =2; i<=number; i++){
            for (int j=0; j<i; j++){
                f[i]=f[i]+f[j];
            }
        }
       return f[number];
    }                            
};

继续优化：
第n级

第n-1级

所以：


继续有一下推论：
应该是
暴力法2：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0 || number == 1) return 1;
        int ans=1;
        for(int i=2; i<=number; i++){
            ans = ans << 1;
        }
        return ans;
    }
};

或者直接计算：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0 || number == 1) return 1;
        return pow(2,number-1);
    }
};

思路二，递归法：

class Solution {
public:
    int jumpFloorII(int number) {
        if (number ==0 || number ==1) return 1;
        int ans = 0;
        while(number>=0){
            number--;
            ans = ans + jumpFloorII(number);
        }
        return ans;

    }
};

这里需要重复计算，因此加入记忆，存储已经计算过的；

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

递归法2，利用推导公式：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0 || number == 1) return 1;
        return jumpFloorII(number-1)*2;
    }
};