斐波那契數列 在實際問題上的變種

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

1 利用數組結構遍歷方法

if(target==1?||?target==0)

return?1;

int?[]?arr?=?new?int?[target+1];

arr[0]?=?1;

arr[1]?=?1;

for(int?i=2;i<=target;i++){

arr[i]?=?arr[i-1]+arr[i-2];

}

return?arr[target];

2 不借助數組結構，采用兩個int型變量和一個while語句中臨時變量temp

if(target==1?||?target==0)

return?1;

int?num1?=?1,num2?=?1;

while(target>1){

int?temp?=?num2;

num2?+=num1;

num1=temp;

target--;

}

return?num2; ? ?

3 遞歸 效率最低

if(target==1?||?target==0)

return?1;

if(target>1)

return?RectCover(target-1)+RectCover(target-2);

return?0;

在這里因為采用了OJ，當我上面的

if(target==1?||?target==0)

return?1;

寫成了

if(target==1)

return?1;

if(target==0)

return?1;

if(target>1)

return?RectCover(target-1)+RectCover(target-2);

return?0;

OJ系統就判斷時間超時了 確實 自己想想 能判斷一次 就解決的問題 ，你為啥要兩次呢