題目描述：
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
比如n=3時，2*3的矩形塊有3種覆蓋方法
思路：
n=4時的情況：
如果到這里，還沒有發(fā)現(xiàn)規(guī)律怎么辦呢？
那我們就再分析以下，從n=3到n=4，怎么來的呢？
這里有2種情況：
直接在n=3的情況下，再后面中添加一個豎著的。這個很顯然成立，有3種情況
然后橫著的顯然能添加到n-2的情況上，也就是在n=2后面，添加2個橫著的。有2種情況
通過以上分析，發(fā)現(xiàn)剛好和圖中的個數(shù)一樣。
所以總結(jié)：f [n]表示2*n大矩陣 的方法數(shù)。
可以得出：f[n] = f[n-1] + f[n-2]，初始條件f[1] = 1, f[2] =2
所以代碼可用遞歸，記憶遞歸，和動態(tài)規(guī)劃和遞推
源代碼：
public class Solution {
? ? public int RectCover(int target)
? ? {
? ? ? ? if(target==0)
? ? ? ? {
? ? ? ? return 0;
? ? ? ? }
? ? ? ? if(target==1)
? ? ? ? {
? ? ? ? return 1;
? ? ? ? }
? ? ? ? if(target==2)
? ? ? ? {
? ? ? ? return 2;
? ? ? ? }
? ? ? ? return RectCover(target-1)+RectCover(target-2);
? ? }
}
