1. Fibonacci數(shù)列

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。
n<=39
注意：不要用從上而下的遞歸，用自下而上，減少下層值的重復(fù)計(jì)算

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0 ||n==1)
            return n;

        int f1=0;
        int f2=1;
        int f3;
        for(int i=2;i<=n;i++){
            f3=f1+f2;
            f1=f2;
            f2=f3;          
        }
        return f3;   
    }
};

2. 跳臺(tái)階

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
思路：f(i)=f(i-1)+f(i-2)

class Solution {
public:
    int jumpFloor(int number) {
        if(number==1 || number==2)
            return number;
        int f1=1;
        int f2=2;
        int f;
        for(int i=3;i<=number;i++){
            f=f1+f2;
            f1=f2;
            f2=f;
        }
        return f;    
    }
};

3. 變態(tài)跳臺(tái)階

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
思路
第n級(jí)臺(tái)階，有n種跳法：
跳1級(jí)，1+f(n-1)
跳2級(jí)，2+f(n-2)
跳3級(jí)，3+f(n-3)
……
f(n)=f(n-1)+f(n-2)+……+f(1)
f(n-1)=f(n-2)+f(n-3)+……+f(1)
所以，f(n)=2*f(n-1)

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

4. 矩形覆蓋

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？
思路
2*n的大矩形，和n個(gè)2*1的小矩形
其中target*2為大矩形的大小
有以下幾種情形：
(1)target<=0, 大矩形<=2*0, 直接return 0；
(2)target=1, 大矩形為2*1，只有一種擺放方法，return 1；
(3)target=2, 大矩形為2*2，有兩種擺放方法，return 2；
(4)target=n, 分2步考慮：
若第一次擺放一塊2*1的小矩陣，則擺放方法有f(target-1)種；
若第一次擺放一塊1*2的小矩陣，對(duì)應(yīng)下方的1*2擺放方法也確定了，則擺放方法有f(target-2)種；
所以f(n)=f(n-1)+f(n-2)。

class Solution {
public:
    int rectCover(int number) {
        if(number==0 || number==1 ||number==2)
            return number;
        
        int f1=1;
        int f2=2;
        int f3;
        for(int i=3;i<=number;i++){
            f3=f1+f2;
            f1=f2;
            f2=f3;
        }
        return f3;    
    }
};