我們可以用 2*1 的小矩形橫著或者豎著去覆寫更大的矩形，請問用 n 個 2*1 的小矩形無重疊地覆寫一個 2*n 的大矩形，總共有多少種方法？
首先來理解一下題意，比如 n = 3 時，2*3 的矩形塊有三種覆寫方法：
這道題目依舊是斐波那契數列，2*n 的大矩形，和 n 個 2*1 的小矩形，其中 target*2 為大矩陣的大小，有以下幾種情形：
-
target <= 0
大矩形為 <= 2*0，直接 return 1
-
target = 1
大矩形為 2*1，只有一種擺放方法，return 1
-
target = 2
大矩形為 2*2，有兩種擺放方法，return 2
-
target = n
分為兩步考慮：
-
第一次擺放一塊 2*1 的小矩陣，則擺放方法總共 f(target - 1)
-
第一次擺放一塊 1*2 的小矩陣，則擺放方法總共為 f(target - 2)，因為擺放了一塊 1*2 的小矩陣，對應下方的 1*2 擺放方法就確定了，所以為 f(target - 2)
-
代碼如下
public class Solution {
public int RectCover(int target) {
if(target <= 0) {
return 0;
} else if(target == 1) {
return 1;
} else if(target == 2) {
return 2;
} else {
return RectCover(target - 1) + RectCover(target - 2);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/128847.html
標籤：其他