《劍指offer》面試題10（題目二）相關題目：矩形覆蓋
題目：我們可以用2 x 1的小矩形橫著或者豎著去覆蓋更大的矩形上渴。請問用n個2 x 1的小矩形無重疊的覆蓋一個2 x n的大矩形，總共有多少種方法？
思路：設2 x n 的大矩形的覆蓋方法共有f （n）種，第一個2 x 1的小矩形去覆蓋大矩形最左邊的時候有2種選擇：橫著放和豎著放。當豎著放的時候疏哗，剩余2 x (n-1)的大矩形共有f（n-1）種方法覆蓋；當2 x 1的小矩形橫著放在左上角的時候禾怠，必須有一個2 x 1的矩形放在左下角返奉，剩余2 x (n-1)的大矩形共有f（n-2）種方法覆蓋。故總共的覆蓋方法f（n）= f（n-1）+ f（n-2）吗氏。
代碼如下：
public int rectangleCover(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
int num1 = 1;
int num2 = 2;
int temp = 0;
for (int i = 3;i <=n;i++) {
temp = num1 + num2;
num1 = num2;
num2 = temp;
}
return temp;
}
}
