劍指offer: 矩形覆寫(循環與遞歸)

題目描述

我們可以用2*1的小矩形橫着或者豎着去覆寫更大的矩形。請問用n個2*1的小矩形無重疊地覆寫一個2*n的大矩形，總共有多少種方法？

分析：

如圖，設n=3，設我們從最左邊開始覆寫，一開始，我們有兩種選擇，豎着放或者橫着放，若橫着放第一塊後，下一塊必然要把4個格子填滿。

然後圖像就分為已經填好的，和還沒填好的。可以看到剩下還沒填好的，其實是初始問題n的一個子問題。

 于是f(n) = f(n-1) + f(n-2),于是這又是一個斐波那契數列問題。

代碼：

int rectCover(int number) {
        if(number<=0) return 0;
        int f0 = 0, f1 = 1;
        int fn = f0 + f1;
        for(int i=2; i<=number;i++){
            f0 = f1;
            f1 = fn;
            fn = f0 + f1;
        }
        return fn;
}