我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形,總共有多少種方法?
public class Solution {
public int RectCover(int target) {
if(target == 1) return 1;
else if(target == 2) return 2;
else{
int res = 0;
int a = 1;
int b = 2;
for(int i=3; i<=target; i++){
res = a + b;
a = b;
b = res;
}
return res;
}
}
}
target=1;return 1;
target=2;return 2;
target > 2;
分兩種情況:第一種情況:第一個豎直放置 target-1種情況;
第二種情況:前兩個位置水平放置,target-2種情況;
綜上:return (target-1)+(target-2)。
即:斐波那契數(shù)列。