我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

首先对此题进行分析：
显然 f(1)=1;f(2)=2
如果有n个小矩形，那么可以分两种情况讨论：
1.第一个小矩形为竖放时，此时有f(n-1)种摆放方式
2.第一个小矩形为横放时，此时前两个小矩形都为横放，此时有f(n-2)种摆放方式
3.第一个小矩形为斜放时，题目不允许
综上，愉快的得出n>2时f(n)=f(n-1)+f(n-2)，就成了斐波那契数列问题
那么就可以简单的写出如下递归：

public class Solution {
    public int RectCover(int target) {
        if(target<=3){         //这题里f(3)=3,就这么写了，写2也没问题
            return target;
        }
        return RectCover(target-1)+RectCover(target-2);
    }
}

说到斐波那契数列，那么对斐波那契数列问题的处理做一下总结（输出第n个斐波那契数列中的数字）：
1.一般的递归方法：

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1){
            return n;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

2.初步优化：
如果是做题，那么写出来递归就行了；但实际上用递归方式计算斐波那契数列实在是太占用资源和时间了，暴力足够，但不美丽，所以我们试试用数组来处理：

public class Solution {
    public int Fibonacci(int n) {
        int []arr = new arr[n+1];
        arr[0]=0;
        arr[1]=1;
        for(int i=2;i<=n;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
}

3.通过之前的优化，显得美丽多了，但是暴力程度又大大下降，怎么让它更暴力一点？能不能丢掉数组？

public class Solution {
    public int Fibonacci(int n) {
        //默认n>0
        int fibo = 1;
        int fibo_1 = 1;
        int fibo_2 = 0;
        for(int i=2;i<=n;i++){
            fibo = fibo_1 + fibo_2;
            fibo_2 = fibo_1;
            fibo_1 = fibo;
        }
        return fibo;
    }
}

4.好了，砍掉数组舒服多了，还能不能再砍点啥？
有了，我们可以观察到，每次fibo_1经过一个循环都会等于fibo，感觉没啥用，那就砍它

public class Solution {
    public int Fibonacci(int n) {
        int fibo = 1;
        int fibo_2 = 0;
        for(int i=2;i<=n;i++){
            fibo = fibo + fibo_2;
            fibo_2 = fibo - fibo_2;
        }
        return fibo;
    }
}

5.究极进化！
从上面可以看到，在for循环里，一共循环了n-1次，而n又不需要作为返回值了，完全可以拿来动刀子嘛，就不用for循环里面还得整个i计数了，直接用n本身来计数

public class Solution {
    public int Fibonacci(int n) {
        int fibo = 1;
        int fibo_2 = 0;
        while(n-->1){      // 直接用n的自减(n--)来计数
            fibo = fibo + fibo_2;
            fibo_2 = fibo - fibo_2
        }
        return fibo;
    }
}

beautiful