題目描述
我們可以用2*1的小矩形橫著或者豎著去覆寫更大的矩形，請問用n個2*1的小矩形無重疊地覆寫一個2*n的大矩形，總共有多少種方法？
思路
斐波那契問題，
時間復雜度O(n)，空間復雜度O(1)，
代碼
public class Solution {
public int RectCover(int target) {
if(target < 1) return 0;
if(target < 3) return target;
int f1 = 1, f2 = 2, tmp = 0;
for(int i = 2; i < target; i++) {
tmp = f1 + f2;
f1 = f2;
f2 = tmp;
}
return f2;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86905.html
標籤：其他
下一篇：選擇排序 C++實作