【劍指offer】10：矩形覆蓋
題目描述：
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
解題思路：
①方法一
對於這種題沒有思路怎麼辦？可以先從最簡單的情況開始考慮：
顯然，當n = 1時，只有一種方法
當n = 2時，如圖有兩種方法
當n = 3時，如圖有三種方法
當我們做到這裡總會出現錯覺，是不是n等於幾就是有幾種方法呢？我們再接著來嘗試：
當n = 4時，如圖有五種方法。
做到這裡基本上會確定就是斐波拉契數列了，可以接著驗證，這裡不做贅述
②方法二
可以先把2X4的覆蓋方法記為f(4)【如上圖n=4時的第一個圖】，用1X2的小矩形去覆蓋時，有兩種選擇：橫著放或者豎著放。當豎著放時，右邊還剩下2X3的區域。很明顯這種情況下覆蓋方法為f(3)。當橫著放時，1X2的矩形放在左上角，其下方區域只能也橫著放一個矩形，此時右邊區域值剩下2X2的區域，這種情況下覆蓋方法為f(2)。所以可以得到：f(4)=f(3)+f(2)，不難看出這仍然是斐波那契數列。
特殊情況：f(1)=1，f(2)=2
程式碼實現
（C實現）：
int rectCover(number) { // write code here int fir = 1, sec = 2, res; if (number <= 0 || number == 1 || number == 2) return number; for (int i = 2; i <number; i++) { res = fir + sec; fir = sec; sec = res; } //res = rectCover(number - 1) + rectCover(number - 2); 遞歸方式 return res; }
（JavaScript實現）：
function rectCover(number) { // write code here var fir = 1, sec = 2, res; if (number <= 0 || number == 1 || number == 2) { return number; } for (var i = 2; i <number; i++) { res = fir + sec; fir = sec; sec = res; } //res = rectCover(number - 1) + rectCover(number - 2); 遞歸方式 return res; }
