1. Fibonacci数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
注意：不要用从上而下的递归，用自下而上，减少下层值的重复计算

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. 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：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. 变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路
第n级台阶，有n种跳法：
跳1级，1+f(n-1)
跳2级，2+f(n-2)
跳3级，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的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路
2*n的大矩形，和n个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的小矩阵，对应下方的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;    
    }
};